        -:    0:Source:/usr/include/c++/9/bits/stl_tree.h
        -:    1:// RB tree implementation -*- C++ -*-
        -:    2:
        -:    3:// Copyright (C) 2001-2019 Free Software Foundation, Inc.
        -:    4://
        -:    5:// This file is part of the GNU ISO C++ Library.  This library is free
        -:    6:// software; you can redistribute it and/or modify it under the
        -:    7:// terms of the GNU General Public License as published by the
        -:    8:// Free Software Foundation; either version 3, or (at your option)
        -:    9:// any later version.
        -:   10:
        -:   11:// This library is distributed in the hope that it will be useful,
        -:   12:// but WITHOUT ANY WARRANTY; without even the implied warranty of
        -:   13:// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
        -:   14:// GNU General Public License for more details.
        -:   15:
        -:   16:// Under Section 7 of GPL version 3, you are granted additional
        -:   17:// permissions described in the GCC Runtime Library Exception, version
        -:   18:// 3.1, as published by the Free Software Foundation.
        -:   19:
        -:   20:// You should have received a copy of the GNU General Public License and
        -:   21:// a copy of the GCC Runtime Library Exception along with this program;
        -:   22:// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
        -:   23:// <http://www.gnu.org/licenses/>.
        -:   24:
        -:   25:/*
        -:   26: *
        -:   27: * Copyright (c) 1996,1997
        -:   28: * Silicon Graphics Computer Systems, Inc.
        -:   29: *
        -:   30: * Permission to use, copy, modify, distribute and sell this software
        -:   31: * and its documentation for any purpose is hereby granted without fee,
        -:   32: * provided that the above copyright notice appear in all copies and
        -:   33: * that both that copyright notice and this permission notice appear
        -:   34: * in supporting documentation.  Silicon Graphics makes no
        -:   35: * representations about the suitability of this software for any
        -:   36: * purpose.  It is provided "as is" without express or implied warranty.
        -:   37: *
        -:   38: *
        -:   39: * Copyright (c) 1994
        -:   40: * Hewlett-Packard Company
        -:   41: *
        -:   42: * Permission to use, copy, modify, distribute and sell this software
        -:   43: * and its documentation for any purpose is hereby granted without fee,
        -:   44: * provided that the above copyright notice appear in all copies and
        -:   45: * that both that copyright notice and this permission notice appear
        -:   46: * in supporting documentation.  Hewlett-Packard Company makes no
        -:   47: * representations about the suitability of this software for any
        -:   48: * purpose.  It is provided "as is" without express or implied warranty.
        -:   49: *
        -:   50: *
        -:   51: */
        -:   52:
        -:   53:/** @file bits/stl_tree.h
        -:   54: *  This is an internal header file, included by other library headers.
        -:   55: *  Do not attempt to use it directly. @headername{map,set}
        -:   56: */
        -:   57:
        -:   58:#ifndef _STL_TREE_H
        -:   59:#define _STL_TREE_H 1
        -:   60:
        -:   61:#pragma GCC system_header
        -:   62:
        -:   63:#include <bits/stl_algobase.h>
        -:   64:#include <bits/allocator.h>
        -:   65:#include <bits/stl_function.h>
        -:   66:#include <bits/cpp_type_traits.h>
        -:   67:#include <ext/alloc_traits.h>
        -:   68:#if __cplusplus >= 201103L
        -:   69:# include <ext/aligned_buffer.h>
        -:   70:#endif
        -:   71:#if __cplusplus > 201402L
        -:   72:# include <bits/node_handle.h>
        -:   73:#endif
        -:   74:
        -:   75:namespace std _GLIBCXX_VISIBILITY(default)
        -:   76:{
        -:   77:_GLIBCXX_BEGIN_NAMESPACE_VERSION
        -:   78:
        -:   79:#if __cplusplus > 201103L
        -:   80:# define __cpp_lib_generic_associative_lookup 201304
        -:   81:#endif
        -:   82:
        -:   83:  // Red-black tree class, designed for use in implementing STL
        -:   84:  // associative containers (set, multiset, map, and multimap). The
        -:   85:  // insertion and deletion algorithms are based on those in Cormen,
        -:   86:  // Leiserson, and Rivest, Introduction to Algorithms (MIT Press,
        -:   87:  // 1990), except that
        -:   88:  //
        -:   89:  // (1) the header cell is maintained with links not only to the root
        -:   90:  // but also to the leftmost node of the tree, to enable constant
        -:   91:  // time begin(), and to the rightmost node of the tree, to enable
        -:   92:  // linear time performance when used with the generic set algorithms
        -:   93:  // (set_union, etc.)
        -:   94:  //
        -:   95:  // (2) when a node being deleted has two children its successor node
        -:   96:  // is relinked into its place, rather than copied, so that the only
        -:   97:  // iterators invalidated are those referring to the deleted node.
        -:   98:
        -:   99:  enum _Rb_tree_color { _S_red = false, _S_black = true };
        -:  100:
        -:  101:  struct _Rb_tree_node_base
        -:  102:  {
        -:  103:    typedef _Rb_tree_node_base* _Base_ptr;
        -:  104:    typedef const _Rb_tree_node_base* _Const_Base_ptr;
        -:  105:
        -:  106:    _Rb_tree_color	_M_color;
        -:  107:    _Base_ptr		_M_parent;
        -:  108:    _Base_ptr		_M_left;
        -:  109:    _Base_ptr		_M_right;
        -:  110:
        -:  111:    static _Base_ptr
        -:  112:    _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  113:    {
        -:  114:      while (__x->_M_left != 0) __x = __x->_M_left;
        -:  115:      return __x;
        -:  116:    }
        -:  117:
        -:  118:    static _Const_Base_ptr
        -:  119:    _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  120:    {
        -:  121:      while (__x->_M_left != 0) __x = __x->_M_left;
        -:  122:      return __x;
        -:  123:    }
        -:  124:
        -:  125:    static _Base_ptr
        -:  126:    _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  127:    {
        -:  128:      while (__x->_M_right != 0) __x = __x->_M_right;
        -:  129:      return __x;
        -:  130:    }
        -:  131:
        -:  132:    static _Const_Base_ptr
        -:  133:    _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  134:    {
        -:  135:      while (__x->_M_right != 0) __x = __x->_M_right;
        -:  136:      return __x;
        -:  137:    }
        -:  138:  };
        -:  139:
        -:  140:  // Helper type offering value initialization guarantee on the compare functor.
        -:  141:  template<typename _Key_compare>
        -:  142:    struct _Rb_tree_key_compare
        -:  143:    {
        -:  144:      _Key_compare		_M_key_compare;
        -:  145:
        -:  146:      _Rb_tree_key_compare()
        -:  147:      _GLIBCXX_NOEXCEPT_IF(
        -:  148:	is_nothrow_default_constructible<_Key_compare>::value)
        -:  149:      : _M_key_compare()
        -:  150:      { }
        -:  151:
        1:  152:      _Rb_tree_key_compare(const _Key_compare& __comp)
        -:  153:      : _M_key_compare(__comp)
        1:  154:      { }
        -:  155:
        -:  156:#if __cplusplus >= 201103L
        -:  157:      // Copy constructor added for consistency with C++98 mode.
        -:  158:      _Rb_tree_key_compare(const _Rb_tree_key_compare&) = default;
        -:  159:
        -:  160:      _Rb_tree_key_compare(_Rb_tree_key_compare&& __x)
        -:  161:	noexcept(is_nothrow_copy_constructible<_Key_compare>::value)
        -:  162:      : _M_key_compare(__x._M_key_compare)
        -:  163:      { }
        -:  164:#endif
        -:  165:    };
        -:  166:
        -:  167:  // Helper type to manage default initialization of node count and header.
        -:  168:  struct _Rb_tree_header
        -:  169:  {
        -:  170:    _Rb_tree_node_base	_M_header;
        -:  171:    size_t		_M_node_count; // Keeps track of size of tree.
        -:  172:
        1:  173:    _Rb_tree_header() _GLIBCXX_NOEXCEPT
        1:  174:    {
        1:  175:      _M_header._M_color = _S_red;
        1:  176:      _M_reset();
        1:  177:    }
        -:  178:
        -:  179:#if __cplusplus >= 201103L
        -:  180:    _Rb_tree_header(_Rb_tree_header&& __x) noexcept
        -:  181:    {
        -:  182:      if (__x._M_header._M_parent != nullptr)
        -:  183:	_M_move_data(__x);
        -:  184:      else
        -:  185:	{
        -:  186:	  _M_header._M_color = _S_red;
        -:  187:	  _M_reset();
        -:  188:	}
        -:  189:    }
        -:  190:#endif
        -:  191:
        -:  192:    void
        -:  193:    _M_move_data(_Rb_tree_header& __from)
        -:  194:    {
        -:  195:      _M_header._M_color = __from._M_header._M_color;
        -:  196:      _M_header._M_parent = __from._M_header._M_parent;
        -:  197:      _M_header._M_left = __from._M_header._M_left;
        -:  198:      _M_header._M_right = __from._M_header._M_right;
        -:  199:      _M_header._M_parent->_M_parent = &_M_header;
        -:  200:      _M_node_count = __from._M_node_count;
        -:  201:
        -:  202:      __from._M_reset();
        -:  203:    }
        -:  204:
        -:  205:    void
        1:  206:    _M_reset()
        -:  207:    {
        1:  208:      _M_header._M_parent = 0;
        1:  209:      _M_header._M_left = &_M_header;
        1:  210:      _M_header._M_right = &_M_header;
        1:  211:      _M_node_count = 0;
        1:  212:    }
        -:  213:  };
        -:  214:
        -:  215:  template<typename _Val>
        -:  216:    struct _Rb_tree_node : public _Rb_tree_node_base
        -:  217:    {
        -:  218:      typedef _Rb_tree_node<_Val>* _Link_type;
        -:  219:
        -:  220:#if __cplusplus < 201103L
        -:  221:      _Val _M_value_field;
        -:  222:
        -:  223:      _Val*
        -:  224:      _M_valptr()
        -:  225:      { return std::__addressof(_M_value_field); }
        -:  226:
        -:  227:      const _Val*
        -:  228:      _M_valptr() const
        -:  229:      { return std::__addressof(_M_value_field); }
        -:  230:#else
        -:  231:      __gnu_cxx::__aligned_membuf<_Val> _M_storage;
        -:  232:
        -:  233:      _Val*
      157:  234:      _M_valptr()
      157:  235:      { return _M_storage._M_ptr(); }
        -:  236:
        -:  237:      const _Val*
      702:  238:      _M_valptr() const
      702:  239:      { return _M_storage._M_ptr(); }
        -:  240:#endif
        -:  241:    };
        -:  242:
        -:  243:  _GLIBCXX_PURE _Rb_tree_node_base*
        -:  244:  _Rb_tree_increment(_Rb_tree_node_base* __x) throw ();
        -:  245:
        -:  246:  _GLIBCXX_PURE const _Rb_tree_node_base*
        -:  247:  _Rb_tree_increment(const _Rb_tree_node_base* __x) throw ();
        -:  248:
        -:  249:  _GLIBCXX_PURE _Rb_tree_node_base*
        -:  250:  _Rb_tree_decrement(_Rb_tree_node_base* __x) throw ();
        -:  251:
        -:  252:  _GLIBCXX_PURE const _Rb_tree_node_base*
        -:  253:  _Rb_tree_decrement(const _Rb_tree_node_base* __x) throw ();
        -:  254:
        -:  255:  template<typename _Tp>
        -:  256:    struct _Rb_tree_iterator
        -:  257:    {
        -:  258:      typedef _Tp  value_type;
        -:  259:      typedef _Tp& reference;
        -:  260:      typedef _Tp* pointer;
        -:  261:
        -:  262:      typedef bidirectional_iterator_tag iterator_category;
        -:  263:      typedef ptrdiff_t			 difference_type;
        -:  264:
        -:  265:      typedef _Rb_tree_iterator<_Tp>		_Self;
        -:  266:      typedef _Rb_tree_node_base::_Base_ptr	_Base_ptr;
        -:  267:      typedef _Rb_tree_node<_Tp>*		_Link_type;
        -:  268:
        -:  269:      _Rb_tree_iterator() _GLIBCXX_NOEXCEPT
        -:  270:      : _M_node() { }
        -:  271:
        -:  272:      explicit
      329:  273:      _Rb_tree_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
      329:  274:      : _M_node(__x) { }
        -:  275:
        -:  276:      reference
        -:  277:      operator*() const _GLIBCXX_NOEXCEPT
        -:  278:      { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
        -:  279:
        -:  280:      pointer
        -:  281:      operator->() const _GLIBCXX_NOEXCEPT
        -:  282:      { return static_cast<_Link_type> (_M_node)->_M_valptr(); }
        -:  283:
        -:  284:      _Self&
    #####:  285:      operator++() _GLIBCXX_NOEXCEPT
        -:  286:      {
    #####:  287:	_M_node = _Rb_tree_increment(_M_node);
    #####:  288:	return *this;
        -:  289:      }
        -:  290:
        -:  291:      _Self
        -:  292:      operator++(int) _GLIBCXX_NOEXCEPT
        -:  293:      {
        -:  294:	_Self __tmp = *this;
        -:  295:	_M_node = _Rb_tree_increment(_M_node);
        -:  296:	return __tmp;
        -:  297:      }
        -:  298:
        -:  299:      _Self&
    #####:  300:      operator--() _GLIBCXX_NOEXCEPT
        -:  301:      {
    #####:  302:	_M_node = _Rb_tree_decrement(_M_node);
    #####:  303:	return *this;
        -:  304:      }
        -:  305:
        -:  306:      _Self
        -:  307:      operator--(int) _GLIBCXX_NOEXCEPT
        -:  308:      {
        -:  309:	_Self __tmp = *this;
        -:  310:	_M_node = _Rb_tree_decrement(_M_node);
        -:  311:	return __tmp;
        -:  312:      }
        -:  313:
        -:  314:      friend bool
        -:  315:      operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
        -:  316:      { return __x._M_node == __y._M_node; }
        -:  317:
        -:  318:      friend bool
        -:  319:      operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
        -:  320:      { return __x._M_node != __y._M_node; }
        -:  321:
        -:  322:      _Base_ptr _M_node;
        -:  323:  };
        -:  324:
        -:  325:  template<typename _Tp>
        -:  326:    struct _Rb_tree_const_iterator
        -:  327:    {
        -:  328:      typedef _Tp	 value_type;
        -:  329:      typedef const _Tp& reference;
        -:  330:      typedef const _Tp* pointer;
        -:  331:
        -:  332:      typedef _Rb_tree_iterator<_Tp> iterator;
        -:  333:
        -:  334:      typedef bidirectional_iterator_tag iterator_category;
        -:  335:      typedef ptrdiff_t			 difference_type;
        -:  336:
        -:  337:      typedef _Rb_tree_const_iterator<_Tp>		_Self;
        -:  338:      typedef _Rb_tree_node_base::_Const_Base_ptr	_Base_ptr;
        -:  339:      typedef const _Rb_tree_node<_Tp>*			_Link_type;
        -:  340:
        -:  341:      _Rb_tree_const_iterator() _GLIBCXX_NOEXCEPT
        -:  342:      : _M_node() { }
        -:  343:
        -:  344:      explicit
      144:  345:      _Rb_tree_const_iterator(_Base_ptr __x) _GLIBCXX_NOEXCEPT
      144:  346:      : _M_node(__x) { }
        -:  347:
      157:  348:      _Rb_tree_const_iterator(const iterator& __it) _GLIBCXX_NOEXCEPT
      157:  349:      : _M_node(__it._M_node) { }
        -:  350:
        -:  351:      iterator
        -:  352:      _M_const_cast() const _GLIBCXX_NOEXCEPT
        -:  353:      { return iterator(const_cast<typename iterator::_Base_ptr>(_M_node)); }
        -:  354:
        -:  355:      reference
        -:  356:      operator*() const _GLIBCXX_NOEXCEPT
        -:  357:      { return *static_cast<_Link_type>(_M_node)->_M_valptr(); }
        -:  358:
        -:  359:      pointer
        -:  360:      operator->() const _GLIBCXX_NOEXCEPT
        -:  361:      { return static_cast<_Link_type>(_M_node)->_M_valptr(); }
        -:  362:
        -:  363:      _Self&
        -:  364:      operator++() _GLIBCXX_NOEXCEPT
        -:  365:      {
        -:  366:	_M_node = _Rb_tree_increment(_M_node);
        -:  367:	return *this;
        -:  368:      }
        -:  369:
        -:  370:      _Self
        -:  371:      operator++(int) _GLIBCXX_NOEXCEPT
        -:  372:      {
        -:  373:	_Self __tmp = *this;
        -:  374:	_M_node = _Rb_tree_increment(_M_node);
        -:  375:	return __tmp;
        -:  376:      }
        -:  377:
        -:  378:      _Self&
        -:  379:      operator--() _GLIBCXX_NOEXCEPT
        -:  380:      {
        -:  381:	_M_node = _Rb_tree_decrement(_M_node);
        -:  382:	return *this;
        -:  383:      }
        -:  384:
        -:  385:      _Self
        -:  386:      operator--(int) _GLIBCXX_NOEXCEPT
        -:  387:      {
        -:  388:	_Self __tmp = *this;
        -:  389:	_M_node = _Rb_tree_decrement(_M_node);
        -:  390:	return __tmp;
        -:  391:      }
        -:  392:
        -:  393:      friend bool
        -:  394:      operator==(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
        -:  395:      { return __x._M_node == __y._M_node; }
        -:  396:
        -:  397:      friend bool
        -:  398:      operator!=(const _Self& __x, const _Self& __y) _GLIBCXX_NOEXCEPT
        -:  399:      { return __x._M_node != __y._M_node; }
        -:  400:
        -:  401:      _Base_ptr _M_node;
        -:  402:    };
        -:  403:
        -:  404:  void
        -:  405:  _Rb_tree_insert_and_rebalance(const bool __insert_left,
        -:  406:				_Rb_tree_node_base* __x,
        -:  407:				_Rb_tree_node_base* __p,
        -:  408:				_Rb_tree_node_base& __header) throw ();
        -:  409:
        -:  410:  _Rb_tree_node_base*
        -:  411:  _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* const __z,
        -:  412:			       _Rb_tree_node_base& __header) throw ();
        -:  413:
        -:  414:#if __cplusplus >= 201402L
        -:  415:  template<typename _Cmp, typename _SfinaeType, typename = __void_t<>>
        -:  416:    struct __has_is_transparent
        -:  417:    { };
        -:  418:
        -:  419:  template<typename _Cmp, typename _SfinaeType>
        -:  420:    struct __has_is_transparent<_Cmp, _SfinaeType,
        -:  421:				__void_t<typename _Cmp::is_transparent>>
        -:  422:    { typedef void type; };
        -:  423:
        -:  424:  template<typename _Cmp, typename _SfinaeType>
        -:  425:    using __has_is_transparent_t
        -:  426:      = typename __has_is_transparent<_Cmp, _SfinaeType>::type;
        -:  427:#endif
        -:  428:
        -:  429:#if __cplusplus > 201402L
        -:  430:  template<typename _Tree1, typename _Cmp2>
        -:  431:    struct _Rb_tree_merge_helper { };
        -:  432:#endif
        -:  433:
        -:  434:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -:  435:	   typename _Compare, typename _Alloc = allocator<_Val> >
        -:  436:    class _Rb_tree
        -:  437:    {
        -:  438:      typedef typename __gnu_cxx::__alloc_traits<_Alloc>::template
        -:  439:	rebind<_Rb_tree_node<_Val> >::other _Node_allocator;
        -:  440:
        -:  441:      typedef __gnu_cxx::__alloc_traits<_Node_allocator> _Alloc_traits;
        -:  442:
        -:  443:    protected:
        -:  444:      typedef _Rb_tree_node_base* 		_Base_ptr;
        -:  445:      typedef const _Rb_tree_node_base* 	_Const_Base_ptr;
        -:  446:      typedef _Rb_tree_node<_Val>* 		_Link_type;
        -:  447:      typedef const _Rb_tree_node<_Val>*	_Const_Link_type;
        -:  448:
        -:  449:    private:
        -:  450:      // Functor recycling a pool of nodes and using allocation once the pool
        -:  451:      // is empty.
        -:  452:      struct _Reuse_or_alloc_node
        -:  453:      {
        -:  454:	_Reuse_or_alloc_node(_Rb_tree& __t)
        -:  455:	: _M_root(__t._M_root()), _M_nodes(__t._M_rightmost()), _M_t(__t)
        -:  456:	{
        -:  457:	  if (_M_root)
        -:  458:	    {
        -:  459:	      _M_root->_M_parent = 0;
        -:  460:
        -:  461:	      if (_M_nodes->_M_left)
        -:  462:		_M_nodes = _M_nodes->_M_left;
        -:  463:	    }
        -:  464:	  else
        -:  465:	    _M_nodes = 0;
        -:  466:	}
        -:  467:
        -:  468:#if __cplusplus >= 201103L
        -:  469:	_Reuse_or_alloc_node(const _Reuse_or_alloc_node&) = delete;
        -:  470:#endif
        -:  471:
        -:  472:	~_Reuse_or_alloc_node()
        -:  473:	{ _M_t._M_erase(static_cast<_Link_type>(_M_root)); }
        -:  474:
        -:  475:	template<typename _Arg>
        -:  476:	  _Link_type
        -:  477:#if __cplusplus < 201103L
        -:  478:	  operator()(const _Arg& __arg)
        -:  479:#else
        -:  480:	  operator()(_Arg&& __arg)
        -:  481:#endif
        -:  482:	  {
        -:  483:	    _Link_type __node = static_cast<_Link_type>(_M_extract());
        -:  484:	    if (__node)
        -:  485:	      {
        -:  486:		_M_t._M_destroy_node(__node);
        -:  487:		_M_t._M_construct_node(__node, _GLIBCXX_FORWARD(_Arg, __arg));
        -:  488:		return __node;
        -:  489:	      }
        -:  490:
        -:  491:	    return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg));
        -:  492:	  }
        -:  493:
        -:  494:      private:
        -:  495:	_Base_ptr
        -:  496:	_M_extract()
        -:  497:	{
        -:  498:	  if (!_M_nodes)
        -:  499:	    return _M_nodes;
        -:  500:
        -:  501:	  _Base_ptr __node = _M_nodes;
        -:  502:	  _M_nodes = _M_nodes->_M_parent;
        -:  503:	  if (_M_nodes)
        -:  504:	    {
        -:  505:	      if (_M_nodes->_M_right == __node)
        -:  506:		{
        -:  507:		  _M_nodes->_M_right = 0;
        -:  508:
        -:  509:		  if (_M_nodes->_M_left)
        -:  510:		    {
        -:  511:		      _M_nodes = _M_nodes->_M_left;
        -:  512:
        -:  513:		      while (_M_nodes->_M_right)
        -:  514:			_M_nodes = _M_nodes->_M_right;
        -:  515:
        -:  516:		      if (_M_nodes->_M_left)
        -:  517:			_M_nodes = _M_nodes->_M_left;
        -:  518:		    }
        -:  519:		}
        -:  520:	      else // __node is on the left.
        -:  521:		_M_nodes->_M_left = 0;
        -:  522:	    }
        -:  523:	  else
        -:  524:	    _M_root = 0;
        -:  525:
        -:  526:	  return __node;
        -:  527:	}
        -:  528:
        -:  529:	_Base_ptr _M_root;
        -:  530:	_Base_ptr _M_nodes;
        -:  531:	_Rb_tree& _M_t;
        -:  532:      };
        -:  533:
        -:  534:      // Functor similar to the previous one but without any pool of nodes to
        -:  535:      // recycle.
        -:  536:      struct _Alloc_node
        -:  537:      {
        1:  538:	_Alloc_node(_Rb_tree& __t)
        1:  539:	: _M_t(__t) { }
        -:  540:
        -:  541:	template<typename _Arg>
        -:  542:	  _Link_type
        -:  543:#if __cplusplus < 201103L
        -:  544:	  operator()(const _Arg& __arg) const
        -:  545:#else
        -:  546:	  operator()(_Arg&& __arg) const
        -:  547:#endif
        -:  548:	  { return _M_t._M_create_node(_GLIBCXX_FORWARD(_Arg, __arg)); }
        -:  549:
        -:  550:      private:
        -:  551:	_Rb_tree& _M_t;
        -:  552:      };
        -:  553:
        -:  554:    public:
        -:  555:      typedef _Key 				key_type;
        -:  556:      typedef _Val 				value_type;
        -:  557:      typedef value_type* 			pointer;
        -:  558:      typedef const value_type* 		const_pointer;
        -:  559:      typedef value_type& 			reference;
        -:  560:      typedef const value_type& 		const_reference;
        -:  561:      typedef size_t 				size_type;
        -:  562:      typedef ptrdiff_t 			difference_type;
        -:  563:      typedef _Alloc 				allocator_type;
        -:  564:
        -:  565:      _Node_allocator&
        -:  566:      _M_get_Node_allocator() _GLIBCXX_NOEXCEPT
        -:  567:      { return this->_M_impl; }
        -:  568:
        -:  569:      const _Node_allocator&
        -:  570:      _M_get_Node_allocator() const _GLIBCXX_NOEXCEPT
        -:  571:      { return this->_M_impl; }
        -:  572:
        -:  573:      allocator_type
        -:  574:      get_allocator() const _GLIBCXX_NOEXCEPT
        -:  575:      { return allocator_type(_M_get_Node_allocator()); }
        -:  576:
        -:  577:    protected:
        -:  578:      _Link_type
        -:  579:      _M_get_node()
        -:  580:      { return _Alloc_traits::allocate(_M_get_Node_allocator(), 1); }
        -:  581:
        -:  582:      void
        -:  583:      _M_put_node(_Link_type __p) _GLIBCXX_NOEXCEPT
        -:  584:      { _Alloc_traits::deallocate(_M_get_Node_allocator(), __p, 1); }
        -:  585:
        -:  586:#if __cplusplus < 201103L
        -:  587:      void
        -:  588:      _M_construct_node(_Link_type __node, const value_type& __x)
        -:  589:      {
        -:  590:	__try
        -:  591:	  { get_allocator().construct(__node->_M_valptr(), __x); }
        -:  592:	__catch(...)
        -:  593:	  {
        -:  594:	    _M_put_node(__node);
        -:  595:	    __throw_exception_again;
        -:  596:	  }
        -:  597:      }
        -:  598:
        -:  599:      _Link_type
        -:  600:      _M_create_node(const value_type& __x)
        -:  601:      {
        -:  602:	_Link_type __tmp = _M_get_node();
        -:  603:	_M_construct_node(__tmp, __x);
        -:  604:	return __tmp;
        -:  605:      }
        -:  606:#else
        -:  607:      template<typename... _Args>
        -:  608:	void
        -:  609:	_M_construct_node(_Link_type __node, _Args&&... __args)
        -:  610:	{
        -:  611:	  __try
        -:  612:	    {
        -:  613:	      ::new(__node) _Rb_tree_node<_Val>;
        -:  614:	      _Alloc_traits::construct(_M_get_Node_allocator(),
        -:  615:				       __node->_M_valptr(),
        -:  616:				       std::forward<_Args>(__args)...);
        -:  617:	    }
        -:  618:	  __catch(...)
        -:  619:	    {
        -:  620:	      __node->~_Rb_tree_node<_Val>();
        -:  621:	      _M_put_node(__node);
        -:  622:	      __throw_exception_again;
        -:  623:	    }
        -:  624:	}
        -:  625:
        -:  626:      template<typename... _Args>
        -:  627:	_Link_type
        -:  628:	_M_create_node(_Args&&... __args)
        -:  629:	{
        -:  630:	  _Link_type __tmp = _M_get_node();
        -:  631:	  _M_construct_node(__tmp, std::forward<_Args>(__args)...);
        -:  632:	  return __tmp;
        -:  633:	}
        -:  634:#endif
        -:  635:
        -:  636:      void
        -:  637:      _M_destroy_node(_Link_type __p) _GLIBCXX_NOEXCEPT
        -:  638:      {
        -:  639:#if __cplusplus < 201103L
        -:  640:	get_allocator().destroy(__p->_M_valptr());
        -:  641:#else
        -:  642:	_Alloc_traits::destroy(_M_get_Node_allocator(), __p->_M_valptr());
        -:  643:	__p->~_Rb_tree_node<_Val>();
        -:  644:#endif
        -:  645:      }
        -:  646:
        -:  647:      void
        -:  648:      _M_drop_node(_Link_type __p) _GLIBCXX_NOEXCEPT
        -:  649:      {
        -:  650:	_M_destroy_node(__p);
        -:  651:	_M_put_node(__p);
        -:  652:      }
        -:  653:
        -:  654:      template<typename _NodeGen>
        -:  655:	_Link_type
        -:  656:	_M_clone_node(_Const_Link_type __x, _NodeGen& __node_gen)
        -:  657:	{
        -:  658:	  _Link_type __tmp = __node_gen(*__x->_M_valptr());
        -:  659:	  __tmp->_M_color = __x->_M_color;
        -:  660:	  __tmp->_M_left = 0;
        -:  661:	  __tmp->_M_right = 0;
        -:  662:	  return __tmp;
        -:  663:	}
        -:  664:
        -:  665:    protected:
        -:  666:#if _GLIBCXX_INLINE_VERSION
        -:  667:      template<typename _Key_compare>
        -:  668:#else
        -:  669:      // Unused _Is_pod_comparator is kept as it is part of mangled name.
        -:  670:      template<typename _Key_compare,
        -:  671:	       bool /* _Is_pod_comparator */ = __is_pod(_Key_compare)>
        -:  672:#endif
        -:  673:	struct _Rb_tree_impl
        -:  674:	: public _Node_allocator
        -:  675:	, public _Rb_tree_key_compare<_Key_compare>
        -:  676:	, public _Rb_tree_header
        -:  677:	{
        -:  678:	  typedef _Rb_tree_key_compare<_Key_compare> _Base_key_compare;
        -:  679:
        -:  680:	  _Rb_tree_impl()
        -:  681:	    _GLIBCXX_NOEXCEPT_IF(
        -:  682:		is_nothrow_default_constructible<_Node_allocator>::value
        -:  683:		&& is_nothrow_default_constructible<_Base_key_compare>::value )
        -:  684:	  : _Node_allocator()
        -:  685:	  { }
        -:  686:
        -:  687:	  _Rb_tree_impl(const _Rb_tree_impl& __x)
        -:  688:	  : _Node_allocator(_Alloc_traits::_S_select_on_copy(__x))
        -:  689:	  , _Base_key_compare(__x._M_key_compare)
        -:  690:	  { }
        -:  691:
        -:  692:#if __cplusplus < 201103L
        -:  693:	  _Rb_tree_impl(const _Key_compare& __comp, const _Node_allocator& __a)
        -:  694:	  : _Node_allocator(__a), _Base_key_compare(__comp)
        -:  695:	  { }
        -:  696:#else
        -:  697:	  _Rb_tree_impl(_Rb_tree_impl&&) = default;
        -:  698:
        -:  699:	  explicit
        -:  700:	  _Rb_tree_impl(_Node_allocator&& __a)
        -:  701:	  : _Node_allocator(std::move(__a))
        -:  702:	  { }
        -:  703:
        -:  704:	  _Rb_tree_impl(_Rb_tree_impl&& __x, _Node_allocator&& __a)
        -:  705:	  : _Node_allocator(std::move(__a)),
        -:  706:	    _Base_key_compare(std::move(__x)),
        -:  707:	    _Rb_tree_header(std::move(__x))
        -:  708:	  { }
        -:  709:
        1:  710:	  _Rb_tree_impl(const _Key_compare& __comp, _Node_allocator&& __a)
        1:  711:	  : _Node_allocator(std::move(__a)), _Base_key_compare(__comp)
        1:  712:	  { }
        -:  713:#endif
        -:  714:	};
        -:  715:
        -:  716:      _Rb_tree_impl<_Compare> _M_impl;
        -:  717:
        -:  718:    protected:
        -:  719:      _Base_ptr&
        -:  720:      _M_root() _GLIBCXX_NOEXCEPT
        -:  721:      { return this->_M_impl._M_header._M_parent; }
        -:  722:
        -:  723:      _Const_Base_ptr
        -:  724:      _M_root() const _GLIBCXX_NOEXCEPT
        -:  725:      { return this->_M_impl._M_header._M_parent; }
        -:  726:
        -:  727:      _Base_ptr&
    #####:  728:      _M_leftmost() _GLIBCXX_NOEXCEPT
    #####:  729:      { return this->_M_impl._M_header._M_left; }
        -:  730:
        -:  731:      _Const_Base_ptr
        -:  732:      _M_leftmost() const _GLIBCXX_NOEXCEPT
        -:  733:      { return this->_M_impl._M_header._M_left; }
        -:  734:
        -:  735:      _Base_ptr&
       12:  736:      _M_rightmost() _GLIBCXX_NOEXCEPT
       12:  737:      { return this->_M_impl._M_header._M_right; }
        -:  738:
        -:  739:      _Const_Base_ptr
        -:  740:      _M_rightmost() const _GLIBCXX_NOEXCEPT
        -:  741:      { return this->_M_impl._M_header._M_right; }
        -:  742:
        -:  743:      _Link_type
        -:  744:      _M_begin() _GLIBCXX_NOEXCEPT
        -:  745:      { return static_cast<_Link_type>(this->_M_impl._M_header._M_parent); }
        -:  746:
        -:  747:      _Const_Link_type
        -:  748:      _M_begin() const _GLIBCXX_NOEXCEPT
        -:  749:      {
        -:  750:	return static_cast<_Const_Link_type>
        -:  751:	  (this->_M_impl._M_header._M_parent);
        -:  752:      }
        -:  753:
        -:  754:      _Base_ptr
      171:  755:      _M_end() _GLIBCXX_NOEXCEPT
      171:  756:      { return &this->_M_impl._M_header; }
        -:  757:
        -:  758:      _Const_Base_ptr
        -:  759:      _M_end() const _GLIBCXX_NOEXCEPT
        -:  760:      { return &this->_M_impl._M_header; }
        -:  761:
        -:  762:      static const_reference
        -:  763:      _S_value(_Const_Link_type __x)
        -:  764:      { return *__x->_M_valptr(); }
        -:  765:
        -:  766:      static const _Key&
      702:  767:      _S_key(_Const_Link_type __x)
        -:  768:      {
        -:  769:#if __cplusplus >= 201103L
        -:  770:	// If we're asking for the key we're presumably using the comparison
        -:  771:	// object, and so this is a good place to sanity check it.
        -:  772:	static_assert(__is_invocable<_Compare&, const _Key&, const _Key&>{},
        -:  773:		      "comparison object must be invocable "
        -:  774:		      "with two arguments of key type");
        -:  775:# if __cplusplus >= 201703L
        -:  776:	// _GLIBCXX_RESOLVE_LIB_DEFECTS
        -:  777:	// 2542. Missing const requirements for associative containers
        -:  778:	if constexpr (__is_invocable<_Compare&, const _Key&, const _Key&>{})
        -:  779:	  static_assert(
        -:  780:	      is_invocable_v<const _Compare&, const _Key&, const _Key&>,
        -:  781:	      "comparison object must be invocable as const");
        -:  782:# endif // C++17
        -:  783:#endif // C++11
        -:  784:
      702:  785:	return _KeyOfValue()(*__x->_M_valptr());
        -:  786:      }
        -:  787:
        -:  788:      static _Link_type
        -:  789:      _S_left(_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  790:      { return static_cast<_Link_type>(__x->_M_left); }
        -:  791:
        -:  792:      static _Const_Link_type
        -:  793:      _S_left(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  794:      { return static_cast<_Const_Link_type>(__x->_M_left); }
        -:  795:
        -:  796:      static _Link_type
        -:  797:      _S_right(_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  798:      { return static_cast<_Link_type>(__x->_M_right); }
        -:  799:
        -:  800:      static _Const_Link_type
        -:  801:      _S_right(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  802:      { return static_cast<_Const_Link_type>(__x->_M_right); }
        -:  803:
        -:  804:      static const_reference
        -:  805:      _S_value(_Const_Base_ptr __x)
        -:  806:      { return *static_cast<_Const_Link_type>(__x)->_M_valptr(); }
        -:  807:
        -:  808:      static const _Key&
      168:  809:      _S_key(_Const_Base_ptr __x)
      168:  810:      { return _S_key(static_cast<_Const_Link_type>(__x)); }
        -:  811:
        -:  812:      static _Base_ptr
        -:  813:      _S_minimum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  814:      { return _Rb_tree_node_base::_S_minimum(__x); }
        -:  815:
        -:  816:      static _Const_Base_ptr
        -:  817:      _S_minimum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  818:      { return _Rb_tree_node_base::_S_minimum(__x); }
        -:  819:
        -:  820:      static _Base_ptr
        -:  821:      _S_maximum(_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  822:      { return _Rb_tree_node_base::_S_maximum(__x); }
        -:  823:
        -:  824:      static _Const_Base_ptr
        -:  825:      _S_maximum(_Const_Base_ptr __x) _GLIBCXX_NOEXCEPT
        -:  826:      { return _Rb_tree_node_base::_S_maximum(__x); }
        -:  827:
        -:  828:    public:
        -:  829:      typedef _Rb_tree_iterator<value_type>       iterator;
        -:  830:      typedef _Rb_tree_const_iterator<value_type> const_iterator;
        -:  831:
        -:  832:      typedef std::reverse_iterator<iterator>       reverse_iterator;
        -:  833:      typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
        -:  834:
        -:  835:#if __cplusplus > 201402L
        -:  836:      using node_type = _Node_handle<_Key, _Val, _Node_allocator>;
        -:  837:      using insert_return_type = _Node_insert_return<
        -:  838:	conditional_t<is_same_v<_Key, _Val>, const_iterator, iterator>,
        -:  839:	node_type>;
        -:  840:#endif
        -:  841:
        -:  842:      pair<_Base_ptr, _Base_ptr>
        -:  843:      _M_get_insert_unique_pos(const key_type& __k);
        -:  844:
        -:  845:      pair<_Base_ptr, _Base_ptr>
        -:  846:      _M_get_insert_equal_pos(const key_type& __k);
        -:  847:
        -:  848:      pair<_Base_ptr, _Base_ptr>
        -:  849:      _M_get_insert_hint_unique_pos(const_iterator __pos,
        -:  850:				    const key_type& __k);
        -:  851:
        -:  852:      pair<_Base_ptr, _Base_ptr>
        -:  853:      _M_get_insert_hint_equal_pos(const_iterator __pos,
        -:  854:				   const key_type& __k);
        -:  855:
        -:  856:    private:
        -:  857:#if __cplusplus >= 201103L
        -:  858:      template<typename _Arg, typename _NodeGen>
        -:  859:	iterator
        -:  860:	_M_insert_(_Base_ptr __x, _Base_ptr __y, _Arg&& __v, _NodeGen&);
        -:  861:
        -:  862:      iterator
        -:  863:      _M_insert_node(_Base_ptr __x, _Base_ptr __y, _Link_type __z);
        -:  864:
        -:  865:      template<typename _Arg>
        -:  866:	iterator
        -:  867:	_M_insert_lower(_Base_ptr __y, _Arg&& __v);
        -:  868:
        -:  869:      template<typename _Arg>
        -:  870:	iterator
        -:  871:	_M_insert_equal_lower(_Arg&& __x);
        -:  872:
        -:  873:      iterator
        -:  874:      _M_insert_lower_node(_Base_ptr __p, _Link_type __z);
        -:  875:
        -:  876:      iterator
        -:  877:      _M_insert_equal_lower_node(_Link_type __z);
        -:  878:#else
        -:  879:      template<typename _NodeGen>
        -:  880:	iterator
        -:  881:	_M_insert_(_Base_ptr __x, _Base_ptr __y,
        -:  882:		   const value_type& __v, _NodeGen&);
        -:  883:
        -:  884:      // _GLIBCXX_RESOLVE_LIB_DEFECTS
        -:  885:      // 233. Insertion hints in associative containers.
        -:  886:      iterator
        -:  887:      _M_insert_lower(_Base_ptr __y, const value_type& __v);
        -:  888:
        -:  889:      iterator
        -:  890:      _M_insert_equal_lower(const value_type& __x);
        -:  891:#endif
        -:  892:
        -:  893:      template<typename _NodeGen>
        -:  894:	_Link_type
        -:  895:	_M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen&);
        -:  896:
        -:  897:      template<typename _NodeGen>
        -:  898:	_Link_type
        -:  899:	_M_copy(const _Rb_tree& __x, _NodeGen& __gen)
        -:  900:	{
        -:  901:	  _Link_type __root = _M_copy(__x._M_begin(), _M_end(), __gen);
        -:  902:	  _M_leftmost() = _S_minimum(__root);
        -:  903:	  _M_rightmost() = _S_maximum(__root);
        -:  904:	  _M_impl._M_node_count = __x._M_impl._M_node_count;
        -:  905:	  return __root;
        -:  906:	}
        -:  907:
        -:  908:      _Link_type
        -:  909:      _M_copy(const _Rb_tree& __x)
        -:  910:      {
        -:  911:	_Alloc_node __an(*this);
        -:  912:	return _M_copy(__x, __an);
        -:  913:      }
        -:  914:
        -:  915:      void
        -:  916:      _M_erase(_Link_type __x);
        -:  917:
        -:  918:      iterator
        -:  919:      _M_lower_bound(_Link_type __x, _Base_ptr __y,
        -:  920:		     const _Key& __k);
        -:  921:
        -:  922:      const_iterator
        -:  923:      _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
        -:  924:		     const _Key& __k) const;
        -:  925:
        -:  926:      iterator
        -:  927:      _M_upper_bound(_Link_type __x, _Base_ptr __y,
        -:  928:		     const _Key& __k);
        -:  929:
        -:  930:      const_iterator
        -:  931:      _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
        -:  932:		     const _Key& __k) const;
        -:  933:
        -:  934:    public:
        -:  935:      // allocation/deallocation
        -:  936:#if __cplusplus < 201103L
        -:  937:      _Rb_tree() { }
        -:  938:#else
        -:  939:      _Rb_tree() = default;
        -:  940:#endif
        -:  941:
        1:  942:      _Rb_tree(const _Compare& __comp,
        -:  943:	       const allocator_type& __a = allocator_type())
        1:  944:      : _M_impl(__comp, _Node_allocator(__a)) { }
        -:  945:
        -:  946:      _Rb_tree(const _Rb_tree& __x)
        -:  947:      : _M_impl(__x._M_impl)
        -:  948:      {
        -:  949:	if (__x._M_root() != 0)
        -:  950:	  _M_root() = _M_copy(__x);
        -:  951:      }
        -:  952:
        -:  953:#if __cplusplus >= 201103L
        -:  954:      _Rb_tree(const allocator_type& __a)
        -:  955:      : _M_impl(_Node_allocator(__a))
        -:  956:      { }
        -:  957:
        -:  958:      _Rb_tree(const _Rb_tree& __x, const allocator_type& __a)
        -:  959:      : _M_impl(__x._M_impl._M_key_compare, _Node_allocator(__a))
        -:  960:      {
        -:  961:	if (__x._M_root() != nullptr)
        -:  962:	  _M_root() = _M_copy(__x);
        -:  963:      }
        -:  964:
        -:  965:      _Rb_tree(_Rb_tree&&) = default;
        -:  966:
        -:  967:      _Rb_tree(_Rb_tree&& __x, const allocator_type& __a)
        -:  968:      : _Rb_tree(std::move(__x), _Node_allocator(__a))
        -:  969:      { }
        -:  970:
        -:  971:    private:
        -:  972:      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, true_type)
        -:  973:      noexcept(is_nothrow_default_constructible<_Compare>::value)
        -:  974:      : _M_impl(std::move(__x._M_impl), std::move(__a))
        -:  975:      { }
        -:  976:
        -:  977:      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a, false_type)
        -:  978:      : _M_impl(__x._M_impl._M_key_compare, std::move(__a))
        -:  979:      {
        -:  980:	if (__x._M_root() != nullptr)
        -:  981:	  _M_move_data(__x, false_type{});
        -:  982:      }
        -:  983:
        -:  984:    public:
        -:  985:      _Rb_tree(_Rb_tree&& __x, _Node_allocator&& __a)
        -:  986:      noexcept( noexcept(
        -:  987:	_Rb_tree(std::declval<_Rb_tree&&>(), std::declval<_Node_allocator&&>(),
        -:  988:		 std::declval<typename _Alloc_traits::is_always_equal>())) )
        -:  989:      : _Rb_tree(std::move(__x), std::move(__a),
        -:  990:		 typename _Alloc_traits::is_always_equal{})
        -:  991:      { }
        -:  992:#endif
        -:  993:
        1:  994:      ~_Rb_tree() _GLIBCXX_NOEXCEPT
        1:  995:      { _M_erase(_M_begin()); }
        -:  996:
        -:  997:      _Rb_tree&
        -:  998:      operator=(const _Rb_tree& __x);
        -:  999:
        -: 1000:      // Accessors.
        -: 1001:      _Compare
        -: 1002:      key_comp() const
        -: 1003:      { return _M_impl._M_key_compare; }
        -: 1004:
        -: 1005:      iterator
        -: 1006:      begin() _GLIBCXX_NOEXCEPT
        -: 1007:      { return iterator(this->_M_impl._M_header._M_left); }
        -: 1008:
        -: 1009:      const_iterator
        -: 1010:      begin() const _GLIBCXX_NOEXCEPT
        -: 1011:      { return const_iterator(this->_M_impl._M_header._M_left); }
        -: 1012:
        -: 1013:      iterator
      157: 1014:      end() _GLIBCXX_NOEXCEPT
      157: 1015:      { return iterator(&this->_M_impl._M_header); }
        -: 1016:
        -: 1017:      const_iterator
      144: 1018:      end() const _GLIBCXX_NOEXCEPT
      144: 1019:      { return const_iterator(&this->_M_impl._M_header); }
        -: 1020:
        -: 1021:      reverse_iterator
        -: 1022:      rbegin() _GLIBCXX_NOEXCEPT
        -: 1023:      { return reverse_iterator(end()); }
        -: 1024:
        -: 1025:      const_reverse_iterator
        -: 1026:      rbegin() const _GLIBCXX_NOEXCEPT
        -: 1027:      { return const_reverse_iterator(end()); }
        -: 1028:
        -: 1029:      reverse_iterator
        -: 1030:      rend() _GLIBCXX_NOEXCEPT
        -: 1031:      { return reverse_iterator(begin()); }
        -: 1032:
        -: 1033:      const_reverse_iterator
        -: 1034:      rend() const _GLIBCXX_NOEXCEPT
        -: 1035:      { return const_reverse_iterator(begin()); }
        -: 1036:
        -: 1037:      _GLIBCXX_NODISCARD bool
        -: 1038:      empty() const _GLIBCXX_NOEXCEPT
        -: 1039:      { return _M_impl._M_node_count == 0; }
        -: 1040:
        -: 1041:      size_type
        -: 1042:      size() const _GLIBCXX_NOEXCEPT
        -: 1043:      { return _M_impl._M_node_count; }
        -: 1044:
        -: 1045:      size_type
        -: 1046:      max_size() const _GLIBCXX_NOEXCEPT
        -: 1047:      { return _Alloc_traits::max_size(_M_get_Node_allocator()); }
        -: 1048:
        -: 1049:      void
        -: 1050:      swap(_Rb_tree& __t)
        -: 1051:      _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value);
        -: 1052:
        -: 1053:      // Insert/erase.
        -: 1054:#if __cplusplus >= 201103L
        -: 1055:      template<typename _Arg>
        -: 1056:	pair<iterator, bool>
        -: 1057:	_M_insert_unique(_Arg&& __x);
        -: 1058:
        -: 1059:      template<typename _Arg>
        -: 1060:	iterator
        -: 1061:	_M_insert_equal(_Arg&& __x);
        -: 1062:
        -: 1063:      template<typename _Arg, typename _NodeGen>
        -: 1064:	iterator
        -: 1065:	_M_insert_unique_(const_iterator __pos, _Arg&& __x, _NodeGen&);
        -: 1066:
        -: 1067:      template<typename _Arg>
        -: 1068:	iterator
        -: 1069:	_M_insert_unique_(const_iterator __pos, _Arg&& __x)
        -: 1070:	{
        -: 1071:	  _Alloc_node __an(*this);
        -: 1072:	  return _M_insert_unique_(__pos, std::forward<_Arg>(__x), __an);
        -: 1073:	}
        -: 1074:
        -: 1075:      template<typename _Arg, typename _NodeGen>
        -: 1076:	iterator
        -: 1077:	_M_insert_equal_(const_iterator __pos, _Arg&& __x, _NodeGen&);
        -: 1078:
        -: 1079:      template<typename _Arg>
        -: 1080:	iterator
        -: 1081:	_M_insert_equal_(const_iterator __pos, _Arg&& __x)
        -: 1082:	{
        -: 1083:	  _Alloc_node __an(*this);
        -: 1084:	  return _M_insert_equal_(__pos, std::forward<_Arg>(__x), __an);
        -: 1085:	}
        -: 1086:
        -: 1087:      template<typename... _Args>
        -: 1088:	pair<iterator, bool>
        -: 1089:	_M_emplace_unique(_Args&&... __args);
        -: 1090:
        -: 1091:      template<typename... _Args>
        -: 1092:	iterator
        -: 1093:	_M_emplace_equal(_Args&&... __args);
        -: 1094:
        -: 1095:      template<typename... _Args>
        -: 1096:	iterator
        -: 1097:	_M_emplace_hint_unique(const_iterator __pos, _Args&&... __args);
        -: 1098:
        -: 1099:      template<typename... _Args>
        -: 1100:	iterator
        -: 1101:	_M_emplace_hint_equal(const_iterator __pos, _Args&&... __args);
        -: 1102:
        -: 1103:      template<typename _Iter>
        -: 1104:	using __same_value_type
        -: 1105:	  = is_same<value_type, typename iterator_traits<_Iter>::value_type>;
        -: 1106:
        -: 1107:      template<typename _InputIterator>
        -: 1108:	__enable_if_t<__same_value_type<_InputIterator>::value>
        1: 1109:	_M_insert_range_unique(_InputIterator __first, _InputIterator __last)
        -: 1110:	{
        1: 1111:	  _Alloc_node __an(*this);
       14: 1112:	  for (; __first != __last; ++__first)
       13: 1113:	    _M_insert_unique_(end(), *__first, __an);
        1: 1114:	}
        -: 1115:
        -: 1116:      template<typename _InputIterator>
        -: 1117:	__enable_if_t<!__same_value_type<_InputIterator>::value>
        -: 1118:	_M_insert_range_unique(_InputIterator __first, _InputIterator __last)
        -: 1119:	{
        -: 1120:	  for (; __first != __last; ++__first)
        -: 1121:	    _M_emplace_unique(*__first);
        -: 1122:	}
        -: 1123:
        -: 1124:      template<typename _InputIterator>
        -: 1125:	__enable_if_t<__same_value_type<_InputIterator>::value>
        -: 1126:	_M_insert_range_equal(_InputIterator __first, _InputIterator __last)
        -: 1127:	{
        -: 1128:	  _Alloc_node __an(*this);
        -: 1129:	  for (; __first != __last; ++__first)
        -: 1130:	    _M_insert_equal_(end(), *__first, __an);
        -: 1131:	}
        -: 1132:
        -: 1133:      template<typename _InputIterator>
        -: 1134:	__enable_if_t<!__same_value_type<_InputIterator>::value>
        -: 1135:	_M_insert_range_equal(_InputIterator __first, _InputIterator __last)
        -: 1136:	{
        -: 1137:	  _Alloc_node __an(*this);
        -: 1138:	  for (; __first != __last; ++__first)
        -: 1139:	    _M_emplace_equal(*__first);
        -: 1140:	}
        -: 1141:#else
        -: 1142:      pair<iterator, bool>
        -: 1143:      _M_insert_unique(const value_type& __x);
        -: 1144:
        -: 1145:      iterator
        -: 1146:      _M_insert_equal(const value_type& __x);
        -: 1147:
        -: 1148:      template<typename _NodeGen>
        -: 1149:	iterator
        -: 1150:	_M_insert_unique_(const_iterator __pos, const value_type& __x,
        -: 1151:			  _NodeGen&);
        -: 1152:
        -: 1153:      iterator
        -: 1154:      _M_insert_unique_(const_iterator __pos, const value_type& __x)
        -: 1155:      {
        -: 1156:	_Alloc_node __an(*this);
        -: 1157:	return _M_insert_unique_(__pos, __x, __an);
        -: 1158:      }
        -: 1159:
        -: 1160:      template<typename _NodeGen>
        -: 1161:	iterator
        -: 1162:	_M_insert_equal_(const_iterator __pos, const value_type& __x,
        -: 1163:			 _NodeGen&);
        -: 1164:      iterator
        -: 1165:      _M_insert_equal_(const_iterator __pos, const value_type& __x)
        -: 1166:      {
        -: 1167:	_Alloc_node __an(*this);
        -: 1168:	return _M_insert_equal_(__pos, __x, __an);
        -: 1169:      }
        -: 1170:
        -: 1171:      template<typename _InputIterator>
        -: 1172:	void
        -: 1173:	_M_insert_range_unique(_InputIterator __first, _InputIterator __last)
        -: 1174:	{
        -: 1175:	  _Alloc_node __an(*this);
        -: 1176:	  for (; __first != __last; ++__first)
        -: 1177:	    _M_insert_unique_(end(), *__first, __an);
        -: 1178:	}
        -: 1179:
        -: 1180:      template<typename _InputIterator>
        -: 1181:	void
        -: 1182:	_M_insert_range_equal(_InputIterator __first, _InputIterator __last)
        -: 1183:	{
        -: 1184:	  _Alloc_node __an(*this);
        -: 1185:	  for (; __first != __last; ++__first)
        -: 1186:	    _M_insert_equal_(end(), *__first, __an);
        -: 1187:	}
        -: 1188:#endif
        -: 1189:
        -: 1190:    private:
        -: 1191:      void
        -: 1192:      _M_erase_aux(const_iterator __position);
        -: 1193:
        -: 1194:      void
        -: 1195:      _M_erase_aux(const_iterator __first, const_iterator __last);
        -: 1196:
        -: 1197:    public:
        -: 1198:#if __cplusplus >= 201103L
        -: 1199:      // _GLIBCXX_RESOLVE_LIB_DEFECTS
        -: 1200:      // DR 130. Associative erase should return an iterator.
        -: 1201:      _GLIBCXX_ABI_TAG_CXX11
        -: 1202:      iterator
        -: 1203:      erase(const_iterator __position)
        -: 1204:      {
        -: 1205:	__glibcxx_assert(__position != end());
        -: 1206:	const_iterator __result = __position;
        -: 1207:	++__result;
        -: 1208:	_M_erase_aux(__position);
        -: 1209:	return __result._M_const_cast();
        -: 1210:      }
        -: 1211:
        -: 1212:      // LWG 2059.
        -: 1213:      _GLIBCXX_ABI_TAG_CXX11
        -: 1214:      iterator
        -: 1215:      erase(iterator __position)
        -: 1216:      {
        -: 1217:	__glibcxx_assert(__position != end());
        -: 1218:	iterator __result = __position;
        -: 1219:	++__result;
        -: 1220:	_M_erase_aux(__position);
        -: 1221:	return __result;
        -: 1222:      }
        -: 1223:#else
        -: 1224:      void
        -: 1225:      erase(iterator __position)
        -: 1226:      {
        -: 1227:	__glibcxx_assert(__position != end());
        -: 1228:	_M_erase_aux(__position);
        -: 1229:      }
        -: 1230:
        -: 1231:      void
        -: 1232:      erase(const_iterator __position)
        -: 1233:      {
        -: 1234:	__glibcxx_assert(__position != end());
        -: 1235:	_M_erase_aux(__position);
        -: 1236:      }
        -: 1237:#endif
        -: 1238:      size_type
        -: 1239:      erase(const key_type& __x);
        -: 1240:
        -: 1241:#if __cplusplus >= 201103L
        -: 1242:      // _GLIBCXX_RESOLVE_LIB_DEFECTS
        -: 1243:      // DR 130. Associative erase should return an iterator.
        -: 1244:      _GLIBCXX_ABI_TAG_CXX11
        -: 1245:      iterator
        -: 1246:      erase(const_iterator __first, const_iterator __last)
        -: 1247:      {
        -: 1248:	_M_erase_aux(__first, __last);
        -: 1249:	return __last._M_const_cast();
        -: 1250:      }
        -: 1251:#else
        -: 1252:      void
        -: 1253:      erase(iterator __first, iterator __last)
        -: 1254:      { _M_erase_aux(__first, __last); }
        -: 1255:
        -: 1256:      void
        -: 1257:      erase(const_iterator __first, const_iterator __last)
        -: 1258:      { _M_erase_aux(__first, __last); }
        -: 1259:#endif
        -: 1260:      void
        -: 1261:      erase(const key_type* __first, const key_type* __last);
        -: 1262:
        -: 1263:      void
        -: 1264:      clear() _GLIBCXX_NOEXCEPT
        -: 1265:      {
        -: 1266:	_M_erase(_M_begin());
        -: 1267:	_M_impl._M_reset();
        -: 1268:      }
        -: 1269:
        -: 1270:      // Set operations.
        -: 1271:      iterator
        -: 1272:      find(const key_type& __k);
        -: 1273:
        -: 1274:      const_iterator
        -: 1275:      find(const key_type& __k) const;
        -: 1276:
        -: 1277:      size_type
        -: 1278:      count(const key_type& __k) const;
        -: 1279:
        -: 1280:      iterator
        -: 1281:      lower_bound(const key_type& __k)
        -: 1282:      { return _M_lower_bound(_M_begin(), _M_end(), __k); }
        -: 1283:
        -: 1284:      const_iterator
        -: 1285:      lower_bound(const key_type& __k) const
        -: 1286:      { return _M_lower_bound(_M_begin(), _M_end(), __k); }
        -: 1287:
        -: 1288:      iterator
        -: 1289:      upper_bound(const key_type& __k)
        -: 1290:      { return _M_upper_bound(_M_begin(), _M_end(), __k); }
        -: 1291:
        -: 1292:      const_iterator
        -: 1293:      upper_bound(const key_type& __k) const
        -: 1294:      { return _M_upper_bound(_M_begin(), _M_end(), __k); }
        -: 1295:
        -: 1296:      pair<iterator, iterator>
        -: 1297:      equal_range(const key_type& __k);
        -: 1298:
        -: 1299:      pair<const_iterator, const_iterator>
        -: 1300:      equal_range(const key_type& __k) const;
        -: 1301:
        -: 1302:#if __cplusplus >= 201402L
        -: 1303:      template<typename _Kt,
        -: 1304:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1305:	iterator
        -: 1306:	_M_find_tr(const _Kt& __k)
        -: 1307:	{
        -: 1308:	  const _Rb_tree* __const_this = this;
        -: 1309:	  return __const_this->_M_find_tr(__k)._M_const_cast();
        -: 1310:	}
        -: 1311:
        -: 1312:      template<typename _Kt,
        -: 1313:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1314:	const_iterator
        -: 1315:	_M_find_tr(const _Kt& __k) const
        -: 1316:	{
        -: 1317:	  auto __j = _M_lower_bound_tr(__k);
        -: 1318:	  if (__j != end() && _M_impl._M_key_compare(__k, _S_key(__j._M_node)))
        -: 1319:	    __j = end();
        -: 1320:	  return __j;
        -: 1321:	}
        -: 1322:
        -: 1323:      template<typename _Kt,
        -: 1324:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1325:	size_type
        -: 1326:	_M_count_tr(const _Kt& __k) const
        -: 1327:	{
        -: 1328:	  auto __p = _M_equal_range_tr(__k);
        -: 1329:	  return std::distance(__p.first, __p.second);
        -: 1330:	}
        -: 1331:
        -: 1332:      template<typename _Kt,
        -: 1333:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1334:	iterator
        -: 1335:	_M_lower_bound_tr(const _Kt& __k)
        -: 1336:	{
        -: 1337:	  const _Rb_tree* __const_this = this;
        -: 1338:	  return __const_this->_M_lower_bound_tr(__k)._M_const_cast();
        -: 1339:	}
        -: 1340:
        -: 1341:      template<typename _Kt,
        -: 1342:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1343:	const_iterator
        -: 1344:	_M_lower_bound_tr(const _Kt& __k) const
        -: 1345:	{
        -: 1346:	  auto __x = _M_begin();
        -: 1347:	  auto __y = _M_end();
        -: 1348:	  while (__x != 0)
        -: 1349:	    if (!_M_impl._M_key_compare(_S_key(__x), __k))
        -: 1350:	      {
        -: 1351:		__y = __x;
        -: 1352:		__x = _S_left(__x);
        -: 1353:	      }
        -: 1354:	    else
        -: 1355:	      __x = _S_right(__x);
        -: 1356:	  return const_iterator(__y);
        -: 1357:	}
        -: 1358:
        -: 1359:      template<typename _Kt,
        -: 1360:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1361:	iterator
        -: 1362:	_M_upper_bound_tr(const _Kt& __k)
        -: 1363:	{
        -: 1364:	  const _Rb_tree* __const_this = this;
        -: 1365:	  return __const_this->_M_upper_bound_tr(__k)._M_const_cast();
        -: 1366:	}
        -: 1367:
        -: 1368:      template<typename _Kt,
        -: 1369:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1370:	const_iterator
        -: 1371:	_M_upper_bound_tr(const _Kt& __k) const
        -: 1372:	{
        -: 1373:	  auto __x = _M_begin();
        -: 1374:	  auto __y = _M_end();
        -: 1375:	  while (__x != 0)
        -: 1376:	    if (_M_impl._M_key_compare(__k, _S_key(__x)))
        -: 1377:	      {
        -: 1378:		__y = __x;
        -: 1379:		__x = _S_left(__x);
        -: 1380:	      }
        -: 1381:	    else
        -: 1382:	      __x = _S_right(__x);
        -: 1383:	  return const_iterator(__y);
        -: 1384:	}
        -: 1385:
        -: 1386:      template<typename _Kt,
        -: 1387:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1388:	pair<iterator, iterator>
        -: 1389:	_M_equal_range_tr(const _Kt& __k)
        -: 1390:	{
        -: 1391:	  const _Rb_tree* __const_this = this;
        -: 1392:	  auto __ret = __const_this->_M_equal_range_tr(__k);
        -: 1393:	  return { __ret.first._M_const_cast(), __ret.second._M_const_cast() };
        -: 1394:	}
        -: 1395:
        -: 1396:      template<typename _Kt,
        -: 1397:	       typename _Req = __has_is_transparent_t<_Compare, _Kt>>
        -: 1398:	pair<const_iterator, const_iterator>
        -: 1399:	_M_equal_range_tr(const _Kt& __k) const
        -: 1400:	{
        -: 1401:	  auto __low = _M_lower_bound_tr(__k);
        -: 1402:	  auto __high = __low;
        -: 1403:	  auto& __cmp = _M_impl._M_key_compare;
        -: 1404:	  while (__high != end() && !__cmp(__k, _S_key(__high._M_node)))
        -: 1405:	    ++__high;
        -: 1406:	  return { __low, __high };
        -: 1407:	}
        -: 1408:#endif
        -: 1409:
        -: 1410:      // Debugging.
        -: 1411:      bool
        -: 1412:      __rb_verify() const;
        -: 1413:
        -: 1414:#if __cplusplus >= 201103L
        -: 1415:      _Rb_tree&
        -: 1416:      operator=(_Rb_tree&&)
        -: 1417:      noexcept(_Alloc_traits::_S_nothrow_move()
        -: 1418:	       && is_nothrow_move_assignable<_Compare>::value);
        -: 1419:
        -: 1420:      template<typename _Iterator>
        -: 1421:	void
        -: 1422:	_M_assign_unique(_Iterator, _Iterator);
        -: 1423:
        -: 1424:      template<typename _Iterator>
        -: 1425:	void
        -: 1426:	_M_assign_equal(_Iterator, _Iterator);
        -: 1427:
        -: 1428:    private:
        -: 1429:      // Move elements from container with equal allocator.
        -: 1430:      void
        -: 1431:      _M_move_data(_Rb_tree& __x, true_type)
        -: 1432:      { _M_impl._M_move_data(__x._M_impl); }
        -: 1433:
        -: 1434:      // Move elements from container with possibly non-equal allocator,
        -: 1435:      // which might result in a copy not a move.
        -: 1436:      void
        -: 1437:      _M_move_data(_Rb_tree&, false_type);
        -: 1438:
        -: 1439:      // Move assignment from container with equal allocator.
        -: 1440:      void
        -: 1441:      _M_move_assign(_Rb_tree&, true_type);
        -: 1442:
        -: 1443:      // Move assignment from container with possibly non-equal allocator,
        -: 1444:      // which might result in a copy not a move.
        -: 1445:      void
        -: 1446:      _M_move_assign(_Rb_tree&, false_type);
        -: 1447:#endif
        -: 1448:
        -: 1449:#if __cplusplus > 201402L
        -: 1450:    public:
        -: 1451:      /// Re-insert an extracted node.
        -: 1452:      insert_return_type
        -: 1453:      _M_reinsert_node_unique(node_type&& __nh)
        -: 1454:      {
        -: 1455:	insert_return_type __ret;
        -: 1456:	if (__nh.empty())
        -: 1457:	  __ret.position = end();
        -: 1458:	else
        -: 1459:	  {
        -: 1460:	    __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
        -: 1461:
        -: 1462:	    auto __res = _M_get_insert_unique_pos(__nh._M_key());
        -: 1463:	    if (__res.second)
        -: 1464:	      {
        -: 1465:		__ret.position
        -: 1466:		  = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
        -: 1467:		__nh._M_ptr = nullptr;
        -: 1468:		__ret.inserted = true;
        -: 1469:	      }
        -: 1470:	    else
        -: 1471:	      {
        -: 1472:		__ret.node = std::move(__nh);
        -: 1473:		__ret.position = iterator(__res.first);
        -: 1474:		__ret.inserted = false;
        -: 1475:	      }
        -: 1476:	  }
        -: 1477:	return __ret;
        -: 1478:      }
        -: 1479:
        -: 1480:      /// Re-insert an extracted node.
        -: 1481:      iterator
        -: 1482:      _M_reinsert_node_equal(node_type&& __nh)
        -: 1483:      {
        -: 1484:	iterator __ret;
        -: 1485:	if (__nh.empty())
        -: 1486:	  __ret = end();
        -: 1487:	else
        -: 1488:	  {
        -: 1489:	    __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
        -: 1490:	    auto __res = _M_get_insert_equal_pos(__nh._M_key());
        -: 1491:	    if (__res.second)
        -: 1492:	      __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
        -: 1493:	    else
        -: 1494:	      __ret = _M_insert_equal_lower_node(__nh._M_ptr);
        -: 1495:	    __nh._M_ptr = nullptr;
        -: 1496:	  }
        -: 1497:	return __ret;
        -: 1498:      }
        -: 1499:
        -: 1500:      /// Re-insert an extracted node.
        -: 1501:      iterator
        -: 1502:      _M_reinsert_node_hint_unique(const_iterator __hint, node_type&& __nh)
        -: 1503:      {
        -: 1504:	iterator __ret;
        -: 1505:	if (__nh.empty())
        -: 1506:	  __ret = end();
        -: 1507:	else
        -: 1508:	  {
        -: 1509:	    __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
        -: 1510:	    auto __res = _M_get_insert_hint_unique_pos(__hint, __nh._M_key());
        -: 1511:	    if (__res.second)
        -: 1512:	      {
        -: 1513:		__ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
        -: 1514:		__nh._M_ptr = nullptr;
        -: 1515:	      }
        -: 1516:	    else
        -: 1517:	      __ret = iterator(__res.first);
        -: 1518:	  }
        -: 1519:	return __ret;
        -: 1520:      }
        -: 1521:
        -: 1522:      /// Re-insert an extracted node.
        -: 1523:      iterator
        -: 1524:      _M_reinsert_node_hint_equal(const_iterator __hint, node_type&& __nh)
        -: 1525:      {
        -: 1526:	iterator __ret;
        -: 1527:	if (__nh.empty())
        -: 1528:	  __ret = end();
        -: 1529:	else
        -: 1530:	  {
        -: 1531:	    __glibcxx_assert(_M_get_Node_allocator() == *__nh._M_alloc);
        -: 1532:	    auto __res = _M_get_insert_hint_equal_pos(__hint, __nh._M_key());
        -: 1533:	    if (__res.second)
        -: 1534:	      __ret = _M_insert_node(__res.first, __res.second, __nh._M_ptr);
        -: 1535:	    else
        -: 1536:	      __ret = _M_insert_equal_lower_node(__nh._M_ptr);
        -: 1537:	    __nh._M_ptr = nullptr;
        -: 1538:	  }
        -: 1539:	return __ret;
        -: 1540:      }
        -: 1541:
        -: 1542:      /// Extract a node.
        -: 1543:      node_type
        -: 1544:      extract(const_iterator __pos)
        -: 1545:      {
        -: 1546:	auto __ptr = _Rb_tree_rebalance_for_erase(
        -: 1547:	    __pos._M_const_cast()._M_node, _M_impl._M_header);
        -: 1548:	--_M_impl._M_node_count;
        -: 1549:	return { static_cast<_Link_type>(__ptr), _M_get_Node_allocator() };
        -: 1550:      }
        -: 1551:
        -: 1552:      /// Extract a node.
        -: 1553:      node_type
        -: 1554:      extract(const key_type& __k)
        -: 1555:      {
        -: 1556:	node_type __nh;
        -: 1557:	auto __pos = find(__k);
        -: 1558:	if (__pos != end())
        -: 1559:	  __nh = extract(const_iterator(__pos));
        -: 1560:	return __nh;
        -: 1561:      }
        -: 1562:
        -: 1563:      template<typename _Compare2>
        -: 1564:	using _Compatible_tree
        -: 1565:	  = _Rb_tree<_Key, _Val, _KeyOfValue, _Compare2, _Alloc>;
        -: 1566:
        -: 1567:      template<typename, typename>
        -: 1568:	friend class _Rb_tree_merge_helper;
        -: 1569:
        -: 1570:      /// Merge from a compatible container into one with unique keys.
        -: 1571:      template<typename _Compare2>
        -: 1572:	void
        -: 1573:	_M_merge_unique(_Compatible_tree<_Compare2>& __src) noexcept
        -: 1574:	{
        -: 1575:	  using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
        -: 1576:	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
        -: 1577:	    {
        -: 1578:	      auto __pos = __i++;
        -: 1579:	      auto __res = _M_get_insert_unique_pos(_KeyOfValue()(*__pos));
        -: 1580:	      if (__res.second)
        -: 1581:		{
        -: 1582:		  auto& __src_impl = _Merge_helper::_S_get_impl(__src);
        -: 1583:		  auto __ptr = _Rb_tree_rebalance_for_erase(
        -: 1584:		      __pos._M_node, __src_impl._M_header);
        -: 1585:		  --__src_impl._M_node_count;
        -: 1586:		  _M_insert_node(__res.first, __res.second,
        -: 1587:				 static_cast<_Link_type>(__ptr));
        -: 1588:		}
        -: 1589:	    }
        -: 1590:	}
        -: 1591:
        -: 1592:      /// Merge from a compatible container into one with equivalent keys.
        -: 1593:      template<typename _Compare2>
        -: 1594:	void
        -: 1595:	_M_merge_equal(_Compatible_tree<_Compare2>& __src) noexcept
        -: 1596:	{
        -: 1597:	  using _Merge_helper = _Rb_tree_merge_helper<_Rb_tree, _Compare2>;
        -: 1598:	  for (auto __i = __src.begin(), __end = __src.end(); __i != __end;)
        -: 1599:	    {
        -: 1600:	      auto __pos = __i++;
        -: 1601:	      auto __res = _M_get_insert_equal_pos(_KeyOfValue()(*__pos));
        -: 1602:	      if (__res.second)
        -: 1603:		{
        -: 1604:		  auto& __src_impl = _Merge_helper::_S_get_impl(__src);
        -: 1605:		  auto __ptr = _Rb_tree_rebalance_for_erase(
        -: 1606:		      __pos._M_node, __src_impl._M_header);
        -: 1607:		  --__src_impl._M_node_count;
        -: 1608:		  _M_insert_node(__res.first, __res.second,
        -: 1609:				 static_cast<_Link_type>(__ptr));
        -: 1610:		}
        -: 1611:	    }
        -: 1612:	}
        -: 1613:#endif // C++17
        -: 1614:
        -: 1615:      friend bool
        -: 1616:      operator==(const _Rb_tree& __x, const _Rb_tree& __y)
        -: 1617:      {
        -: 1618:	return __x.size() == __y.size()
        -: 1619:	  && std::equal(__x.begin(), __x.end(), __y.begin());
        -: 1620:      }
        -: 1621:
        -: 1622:      friend bool
        -: 1623:      operator<(const _Rb_tree& __x, const _Rb_tree& __y)
        -: 1624:      {
        -: 1625:	return std::lexicographical_compare(__x.begin(), __x.end(),
        -: 1626:					    __y.begin(), __y.end());
        -: 1627:      }
        -: 1628:
        -: 1629:      friend bool _GLIBCXX_DEPRECATED
        -: 1630:      operator!=(const _Rb_tree& __x, const _Rb_tree& __y)
        -: 1631:      { return !(__x == __y); }
        -: 1632:
        -: 1633:      friend bool _GLIBCXX_DEPRECATED
        -: 1634:      operator>(const _Rb_tree& __x, const _Rb_tree& __y)
        -: 1635:      { return __y < __x; }
        -: 1636:
        -: 1637:      friend bool _GLIBCXX_DEPRECATED
        -: 1638:      operator<=(const _Rb_tree& __x, const _Rb_tree& __y)
        -: 1639:      { return !(__y < __x); }
        -: 1640:
        -: 1641:      friend bool _GLIBCXX_DEPRECATED
        -: 1642:      operator>=(const _Rb_tree& __x, const _Rb_tree& __y)
        -: 1643:      { return !(__x < __y); }
        -: 1644:    };
        -: 1645:
        -: 1646:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1647:	   typename _Compare, typename _Alloc>
        -: 1648:    inline void
        -: 1649:    swap(_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __x,
        -: 1650:	 _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>& __y)
        -: 1651:    { __x.swap(__y); }
        -: 1652:
        -: 1653:#if __cplusplus >= 201103L
        -: 1654:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1655:	   typename _Compare, typename _Alloc>
        -: 1656:    void
        -: 1657:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1658:    _M_move_data(_Rb_tree& __x, false_type)
        -: 1659:    {
        -: 1660:      if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
        -: 1661:	_M_move_data(__x, true_type());
        -: 1662:      else
        -: 1663:	{
        -: 1664:	  _Alloc_node __an(*this);
        -: 1665:	  auto __lbd =
        -: 1666:	    [&__an](const value_type& __cval)
        -: 1667:	    {
        -: 1668:	      auto& __val = const_cast<value_type&>(__cval);
        -: 1669:	      return __an(std::move_if_noexcept(__val));
        -: 1670:	    };
        -: 1671:	  _M_root() = _M_copy(__x, __lbd);
        -: 1672:	}
        -: 1673:    }
        -: 1674:
        -: 1675:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1676:	   typename _Compare, typename _Alloc>
        -: 1677:    inline void
        -: 1678:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1679:    _M_move_assign(_Rb_tree& __x, true_type)
        -: 1680:    {
        -: 1681:      clear();
        -: 1682:      if (__x._M_root() != nullptr)
        -: 1683:	_M_move_data(__x, true_type());
        -: 1684:      std::__alloc_on_move(_M_get_Node_allocator(),
        -: 1685:			   __x._M_get_Node_allocator());
        -: 1686:    }
        -: 1687:
        -: 1688:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1689:	   typename _Compare, typename _Alloc>
        -: 1690:    void
        -: 1691:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1692:    _M_move_assign(_Rb_tree& __x, false_type)
        -: 1693:    {
        -: 1694:      if (_M_get_Node_allocator() == __x._M_get_Node_allocator())
        -: 1695:	return _M_move_assign(__x, true_type{});
        -: 1696:
        -: 1697:      // Try to move each node reusing existing nodes and copying __x nodes
        -: 1698:      // structure.
        -: 1699:      _Reuse_or_alloc_node __roan(*this);
        -: 1700:      _M_impl._M_reset();
        -: 1701:      if (__x._M_root() != nullptr)
        -: 1702:	{
        -: 1703:	  auto __lbd =
        -: 1704:	    [&__roan](const value_type& __cval)
        -: 1705:	    {
        -: 1706:	      auto& __val = const_cast<value_type&>(__cval);
        -: 1707:	      return __roan(std::move_if_noexcept(__val));
        -: 1708:	    };
        -: 1709:	  _M_root() = _M_copy(__x, __lbd);
        -: 1710:	  __x.clear();
        -: 1711:	}
        -: 1712:    }
        -: 1713:
        -: 1714:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1715:	   typename _Compare, typename _Alloc>
        -: 1716:    inline _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
        -: 1717:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1718:    operator=(_Rb_tree&& __x)
        -: 1719:    noexcept(_Alloc_traits::_S_nothrow_move()
        -: 1720:	     && is_nothrow_move_assignable<_Compare>::value)
        -: 1721:    {
        -: 1722:      _M_impl._M_key_compare = std::move(__x._M_impl._M_key_compare);
        -: 1723:      _M_move_assign(__x, __bool_constant<_Alloc_traits::_S_nothrow_move()>());
        -: 1724:      return *this;
        -: 1725:    }
        -: 1726:
        -: 1727:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1728:	   typename _Compare, typename _Alloc>
        -: 1729:    template<typename _Iterator>
        -: 1730:      void
        -: 1731:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1732:      _M_assign_unique(_Iterator __first, _Iterator __last)
        -: 1733:      {
        -: 1734:	_Reuse_or_alloc_node __roan(*this);
        -: 1735:	_M_impl._M_reset();
        -: 1736:	for (; __first != __last; ++__first)
        -: 1737:	  _M_insert_unique_(end(), *__first, __roan);
        -: 1738:      }
        -: 1739:
        -: 1740:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1741:	   typename _Compare, typename _Alloc>
        -: 1742:    template<typename _Iterator>
        -: 1743:      void
        -: 1744:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1745:      _M_assign_equal(_Iterator __first, _Iterator __last)
        -: 1746:      {
        -: 1747:	_Reuse_or_alloc_node __roan(*this);
        -: 1748:	_M_impl._M_reset();
        -: 1749:	for (; __first != __last; ++__first)
        -: 1750:	  _M_insert_equal_(end(), *__first, __roan);
        -: 1751:      }
        -: 1752:#endif
        -: 1753:
        -: 1754:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1755:	   typename _Compare, typename _Alloc>
        -: 1756:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
        -: 1757:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1758:    operator=(const _Rb_tree& __x)
        -: 1759:    {
        -: 1760:      if (this != &__x)
        -: 1761:	{
        -: 1762:	  // Note that _Key may be a constant type.
        -: 1763:#if __cplusplus >= 201103L
        -: 1764:	  if (_Alloc_traits::_S_propagate_on_copy_assign())
        -: 1765:	    {
        -: 1766:	      auto& __this_alloc = this->_M_get_Node_allocator();
        -: 1767:	      auto& __that_alloc = __x._M_get_Node_allocator();
        -: 1768:	      if (!_Alloc_traits::_S_always_equal()
        -: 1769:		  && __this_alloc != __that_alloc)
        -: 1770:		{
        -: 1771:		  // Replacement allocator cannot free existing storage, we need
        -: 1772:		  // to erase nodes first.
        -: 1773:		  clear();
        -: 1774:		  std::__alloc_on_copy(__this_alloc, __that_alloc);
        -: 1775:		}
        -: 1776:	    }
        -: 1777:#endif
        -: 1778:
        -: 1779:	  _Reuse_or_alloc_node __roan(*this);
        -: 1780:	  _M_impl._M_reset();
        -: 1781:	  _M_impl._M_key_compare = __x._M_impl._M_key_compare;
        -: 1782:	  if (__x._M_root() != 0)
        -: 1783:	    _M_root() = _M_copy(__x, __roan);
        -: 1784:	}
        -: 1785:
        -: 1786:      return *this;
        -: 1787:    }
        -: 1788:
        -: 1789:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1790:	   typename _Compare, typename _Alloc>
        -: 1791:#if __cplusplus >= 201103L
        -: 1792:    template<typename _Arg, typename _NodeGen>
        -: 1793:#else
        -: 1794:    template<typename _NodeGen>
        -: 1795:#endif
        -: 1796:      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
       13: 1797:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1798:      _M_insert_(_Base_ptr __x, _Base_ptr __p,
        -: 1799:#if __cplusplus >= 201103L
        -: 1800:		 _Arg&& __v,
        -: 1801:#else
        -: 1802:		 const _Val& __v,
        -: 1803:#endif
        -: 1804:		 _NodeGen& __node_gen)
        -: 1805:      {
       13: 1806:	bool __insert_left = (__x != 0 || __p == _M_end()
       25: 1807:			      || _M_impl._M_key_compare(_KeyOfValue()(__v),
        -: 1808:							_S_key(__p)));
        -: 1809:
       13: 1810:	_Link_type __z = __node_gen(_GLIBCXX_FORWARD(_Arg, __v));
        -: 1811:
       13: 1812:	_Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
       13: 1813:				      this->_M_impl._M_header);
       13: 1814:	++_M_impl._M_node_count;
       13: 1815:	return iterator(__z);
        -: 1816:      }
        -: 1817:
        -: 1818:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1819:	   typename _Compare, typename _Alloc>
        -: 1820:#if __cplusplus >= 201103L
        -: 1821:    template<typename _Arg>
        -: 1822:#endif
        -: 1823:    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 1824:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1825:#if __cplusplus >= 201103L
        -: 1826:    _M_insert_lower(_Base_ptr __p, _Arg&& __v)
        -: 1827:#else
        -: 1828:    _M_insert_lower(_Base_ptr __p, const _Val& __v)
        -: 1829:#endif
        -: 1830:    {
        -: 1831:      bool __insert_left = (__p == _M_end()
        -: 1832:			    || !_M_impl._M_key_compare(_S_key(__p),
        -: 1833:						       _KeyOfValue()(__v)));
        -: 1834:
        -: 1835:      _Link_type __z = _M_create_node(_GLIBCXX_FORWARD(_Arg, __v));
        -: 1836:
        -: 1837:      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
        -: 1838:				    this->_M_impl._M_header);
        -: 1839:      ++_M_impl._M_node_count;
        -: 1840:      return iterator(__z);
        -: 1841:    }
        -: 1842:
        -: 1843:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1844:	   typename _Compare, typename _Alloc>
        -: 1845:#if __cplusplus >= 201103L
        -: 1846:    template<typename _Arg>
        -: 1847:#endif
        -: 1848:    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 1849:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1850:#if __cplusplus >= 201103L
        -: 1851:    _M_insert_equal_lower(_Arg&& __v)
        -: 1852:#else
        -: 1853:    _M_insert_equal_lower(const _Val& __v)
        -: 1854:#endif
        -: 1855:    {
        -: 1856:      _Link_type __x = _M_begin();
        -: 1857:      _Base_ptr __y = _M_end();
        -: 1858:      while (__x != 0)
        -: 1859:	{
        -: 1860:	  __y = __x;
        -: 1861:	  __x = !_M_impl._M_key_compare(_S_key(__x), _KeyOfValue()(__v)) ?
        -: 1862:		_S_left(__x) : _S_right(__x);
        -: 1863:	}
        -: 1864:      return _M_insert_lower(__y, _GLIBCXX_FORWARD(_Arg, __v));
        -: 1865:    }
        -: 1866:
        -: 1867:  template<typename _Key, typename _Val, typename _KoV,
        -: 1868:	   typename _Compare, typename _Alloc>
        -: 1869:    template<typename _NodeGen>
        -: 1870:      typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
        -: 1871:      _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
        -: 1872:      _M_copy(_Const_Link_type __x, _Base_ptr __p, _NodeGen& __node_gen)
        -: 1873:      {
        -: 1874:	// Structural copy. __x and __p must be non-null.
        -: 1875:	_Link_type __top = _M_clone_node(__x, __node_gen);
        -: 1876:	__top->_M_parent = __p;
        -: 1877:
        -: 1878:	__try
        -: 1879:	  {
        -: 1880:	    if (__x->_M_right)
        -: 1881:	      __top->_M_right = _M_copy(_S_right(__x), __top, __node_gen);
        -: 1882:	    __p = __top;
        -: 1883:	    __x = _S_left(__x);
        -: 1884:
        -: 1885:	    while (__x != 0)
        -: 1886:	      {
        -: 1887:		_Link_type __y = _M_clone_node(__x, __node_gen);
        -: 1888:		__p->_M_left = __y;
        -: 1889:		__y->_M_parent = __p;
        -: 1890:		if (__x->_M_right)
        -: 1891:		  __y->_M_right = _M_copy(_S_right(__x), __y, __node_gen);
        -: 1892:		__p = __y;
        -: 1893:		__x = _S_left(__x);
        -: 1894:	      }
        -: 1895:	  }
        -: 1896:	__catch(...)
        -: 1897:	  {
        -: 1898:	    _M_erase(__top);
        -: 1899:	    __throw_exception_again;
        -: 1900:	  }
        -: 1901:	return __top;
        -: 1902:      }
        -: 1903:
        -: 1904:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1905:	   typename _Compare, typename _Alloc>
        -: 1906:    void
       14: 1907:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1908:    _M_erase(_Link_type __x)
        -: 1909:    {
        -: 1910:      // Erase without rebalancing.
       27: 1911:      while (__x != 0)
        -: 1912:	{
       13: 1913:	  _M_erase(_S_right(__x));
       13: 1914:	  _Link_type __y = _S_left(__x);
       13: 1915:	  _M_drop_node(__x);
        -: 1916:	  __x = __y;
        -: 1917:	}
       14: 1918:    }
        -: 1919:
        -: 1920:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1921:	   typename _Compare, typename _Alloc>
        -: 1922:    typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 1923:		      _Compare, _Alloc>::iterator
      144: 1924:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1925:    _M_lower_bound(_Link_type __x, _Base_ptr __y,
        -: 1926:		   const _Key& __k)
        -: 1927:    {
      678: 1928:      while (__x != 0)
      534: 1929:	if (!_M_impl._M_key_compare(_S_key(__x), __k))
      294: 1930:	  __y = __x, __x = _S_left(__x);
        -: 1931:	else
      240: 1932:	  __x = _S_right(__x);
      144: 1933:      return iterator(__y);
        -: 1934:    }
        -: 1935:
        -: 1936:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1937:	   typename _Compare, typename _Alloc>
        -: 1938:    typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 1939:		      _Compare, _Alloc>::const_iterator
        -: 1940:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1941:    _M_lower_bound(_Const_Link_type __x, _Const_Base_ptr __y,
        -: 1942:		   const _Key& __k) const
        -: 1943:    {
        -: 1944:      while (__x != 0)
        -: 1945:	if (!_M_impl._M_key_compare(_S_key(__x), __k))
        -: 1946:	  __y = __x, __x = _S_left(__x);
        -: 1947:	else
        -: 1948:	  __x = _S_right(__x);
        -: 1949:      return const_iterator(__y);
        -: 1950:    }
        -: 1951:
        -: 1952:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1953:	   typename _Compare, typename _Alloc>
        -: 1954:    typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 1955:		      _Compare, _Alloc>::iterator
        -: 1956:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1957:    _M_upper_bound(_Link_type __x, _Base_ptr __y,
        -: 1958:		   const _Key& __k)
        -: 1959:    {
        -: 1960:      while (__x != 0)
        -: 1961:	if (_M_impl._M_key_compare(__k, _S_key(__x)))
        -: 1962:	  __y = __x, __x = _S_left(__x);
        -: 1963:	else
        -: 1964:	  __x = _S_right(__x);
        -: 1965:      return iterator(__y);
        -: 1966:    }
        -: 1967:
        -: 1968:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1969:	   typename _Compare, typename _Alloc>
        -: 1970:    typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 1971:		      _Compare, _Alloc>::const_iterator
        -: 1972:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1973:    _M_upper_bound(_Const_Link_type __x, _Const_Base_ptr __y,
        -: 1974:		   const _Key& __k) const
        -: 1975:    {
        -: 1976:      while (__x != 0)
        -: 1977:	if (_M_impl._M_key_compare(__k, _S_key(__x)))
        -: 1978:	  __y = __x, __x = _S_left(__x);
        -: 1979:	else
        -: 1980:	  __x = _S_right(__x);
        -: 1981:      return const_iterator(__y);
        -: 1982:    }
        -: 1983:
        -: 1984:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 1985:	   typename _Compare, typename _Alloc>
        -: 1986:    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 1987:			   _Compare, _Alloc>::iterator,
        -: 1988:	 typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 1989:			   _Compare, _Alloc>::iterator>
        -: 1990:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 1991:    equal_range(const _Key& __k)
        -: 1992:    {
        -: 1993:      _Link_type __x = _M_begin();
        -: 1994:      _Base_ptr __y = _M_end();
        -: 1995:      while (__x != 0)
        -: 1996:	{
        -: 1997:	  if (_M_impl._M_key_compare(_S_key(__x), __k))
        -: 1998:	    __x = _S_right(__x);
        -: 1999:	  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
        -: 2000:	    __y = __x, __x = _S_left(__x);
        -: 2001:	  else
        -: 2002:	    {
        -: 2003:	      _Link_type __xu(__x);
        -: 2004:	      _Base_ptr __yu(__y);
        -: 2005:	      __y = __x, __x = _S_left(__x);
        -: 2006:	      __xu = _S_right(__xu);
        -: 2007:	      return pair<iterator,
        -: 2008:			  iterator>(_M_lower_bound(__x, __y, __k),
        -: 2009:				    _M_upper_bound(__xu, __yu, __k));
        -: 2010:	    }
        -: 2011:	}
        -: 2012:      return pair<iterator, iterator>(iterator(__y),
        -: 2013:				      iterator(__y));
        -: 2014:    }
        -: 2015:
        -: 2016:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2017:	   typename _Compare, typename _Alloc>
        -: 2018:    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2019:			   _Compare, _Alloc>::const_iterator,
        -: 2020:	 typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2021:			   _Compare, _Alloc>::const_iterator>
        -: 2022:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2023:    equal_range(const _Key& __k) const
        -: 2024:    {
        -: 2025:      _Const_Link_type __x = _M_begin();
        -: 2026:      _Const_Base_ptr __y = _M_end();
        -: 2027:      while (__x != 0)
        -: 2028:	{
        -: 2029:	  if (_M_impl._M_key_compare(_S_key(__x), __k))
        -: 2030:	    __x = _S_right(__x);
        -: 2031:	  else if (_M_impl._M_key_compare(__k, _S_key(__x)))
        -: 2032:	    __y = __x, __x = _S_left(__x);
        -: 2033:	  else
        -: 2034:	    {
        -: 2035:	      _Const_Link_type __xu(__x);
        -: 2036:	      _Const_Base_ptr __yu(__y);
        -: 2037:	      __y = __x, __x = _S_left(__x);
        -: 2038:	      __xu = _S_right(__xu);
        -: 2039:	      return pair<const_iterator,
        -: 2040:			  const_iterator>(_M_lower_bound(__x, __y, __k),
        -: 2041:					  _M_upper_bound(__xu, __yu, __k));
        -: 2042:	    }
        -: 2043:	}
        -: 2044:      return pair<const_iterator, const_iterator>(const_iterator(__y),
        -: 2045:						  const_iterator(__y));
        -: 2046:    }
        -: 2047:
        -: 2048:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2049:	   typename _Compare, typename _Alloc>
        -: 2050:    void
        -: 2051:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2052:    swap(_Rb_tree& __t)
        -: 2053:    _GLIBCXX_NOEXCEPT_IF(__is_nothrow_swappable<_Compare>::value)
        -: 2054:    {
        -: 2055:      if (_M_root() == 0)
        -: 2056:	{
        -: 2057:	  if (__t._M_root() != 0)
        -: 2058:	    _M_impl._M_move_data(__t._M_impl);
        -: 2059:	}
        -: 2060:      else if (__t._M_root() == 0)
        -: 2061:	__t._M_impl._M_move_data(_M_impl);
        -: 2062:      else
        -: 2063:	{
        -: 2064:	  std::swap(_M_root(),__t._M_root());
        -: 2065:	  std::swap(_M_leftmost(),__t._M_leftmost());
        -: 2066:	  std::swap(_M_rightmost(),__t._M_rightmost());
        -: 2067:
        -: 2068:	  _M_root()->_M_parent = _M_end();
        -: 2069:	  __t._M_root()->_M_parent = __t._M_end();
        -: 2070:	  std::swap(this->_M_impl._M_node_count, __t._M_impl._M_node_count);
        -: 2071:	}
        -: 2072:      // No need to swap header's color as it does not change.
        -: 2073:      std::swap(this->_M_impl._M_key_compare, __t._M_impl._M_key_compare);
        -: 2074:
        -: 2075:      _Alloc_traits::_S_on_swap(_M_get_Node_allocator(),
        -: 2076:				__t._M_get_Node_allocator());
        -: 2077:    }
        -: 2078:
        -: 2079:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2080:	   typename _Compare, typename _Alloc>
        -: 2081:    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2082:			   _Compare, _Alloc>::_Base_ptr,
        -: 2083:	 typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2084:			   _Compare, _Alloc>::_Base_ptr>
        1: 2085:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2086:    _M_get_insert_unique_pos(const key_type& __k)
        -: 2087:    {
        -: 2088:      typedef pair<_Base_ptr, _Base_ptr> _Res;
        1: 2089:      _Link_type __x = _M_begin();
        1: 2090:      _Base_ptr __y = _M_end();
        -: 2091:      bool __comp = true;
       1*: 2092:      while (__x != 0)
        -: 2093:	{
    #####: 2094:	  __y = __x;
    #####: 2095:	  __comp = _M_impl._M_key_compare(__k, _S_key(__x));
    #####: 2096:	  __x = __comp ? _S_left(__x) : _S_right(__x);
        -: 2097:	}
        1: 2098:      iterator __j = iterator(__y);
        1: 2099:      if (__comp)
        -: 2100:	{
        1: 2101:	  if (__j == begin())
        1: 2102:	    return _Res(__x, __y);
        -: 2103:	  else
    #####: 2104:	    --__j;
        -: 2105:	}
    #####: 2106:      if (_M_impl._M_key_compare(_S_key(__j._M_node), __k))
    #####: 2107:	return _Res(__x, __y);
    #####: 2108:      return _Res(__j._M_node, 0);
        -: 2109:    }
        -: 2110:
        -: 2111:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2112:	   typename _Compare, typename _Alloc>
        -: 2113:    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2114:			   _Compare, _Alloc>::_Base_ptr,
        -: 2115:	 typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2116:			   _Compare, _Alloc>::_Base_ptr>
        -: 2117:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2118:    _M_get_insert_equal_pos(const key_type& __k)
        -: 2119:    {
        -: 2120:      typedef pair<_Base_ptr, _Base_ptr> _Res;
        -: 2121:      _Link_type __x = _M_begin();
        -: 2122:      _Base_ptr __y = _M_end();
        -: 2123:      while (__x != 0)
        -: 2124:	{
        -: 2125:	  __y = __x;
        -: 2126:	  __x = _M_impl._M_key_compare(__k, _S_key(__x)) ?
        -: 2127:		_S_left(__x) : _S_right(__x);
        -: 2128:	}
        -: 2129:      return _Res(__x, __y);
        -: 2130:    }
        -: 2131:
        -: 2132:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2133:	   typename _Compare, typename _Alloc>
        -: 2134:#if __cplusplus >= 201103L
        -: 2135:    template<typename _Arg>
        -: 2136:#endif
        -: 2137:    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2138:			   _Compare, _Alloc>::iterator, bool>
        -: 2139:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2140:#if __cplusplus >= 201103L
        -: 2141:    _M_insert_unique(_Arg&& __v)
        -: 2142:#else
        -: 2143:    _M_insert_unique(const _Val& __v)
        -: 2144:#endif
        -: 2145:    {
        -: 2146:      typedef pair<iterator, bool> _Res;
        -: 2147:      pair<_Base_ptr, _Base_ptr> __res
        -: 2148:	= _M_get_insert_unique_pos(_KeyOfValue()(__v));
        -: 2149:
        -: 2150:      if (__res.second)
        -: 2151:	{
        -: 2152:	  _Alloc_node __an(*this);
        -: 2153:	  return _Res(_M_insert_(__res.first, __res.second,
        -: 2154:				 _GLIBCXX_FORWARD(_Arg, __v), __an),
        -: 2155:		      true);
        -: 2156:	}
        -: 2157:
        -: 2158:      return _Res(iterator(__res.first), false);
        -: 2159:    }
        -: 2160:
        -: 2161:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2162:	   typename _Compare, typename _Alloc>
        -: 2163:#if __cplusplus >= 201103L
        -: 2164:    template<typename _Arg>
        -: 2165:#endif
        -: 2166:    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 2167:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2168:#if __cplusplus >= 201103L
        -: 2169:    _M_insert_equal(_Arg&& __v)
        -: 2170:#else
        -: 2171:    _M_insert_equal(const _Val& __v)
        -: 2172:#endif
        -: 2173:    {
        -: 2174:      pair<_Base_ptr, _Base_ptr> __res
        -: 2175:	= _M_get_insert_equal_pos(_KeyOfValue()(__v));
        -: 2176:      _Alloc_node __an(*this);
        -: 2177:      return _M_insert_(__res.first, __res.second,
        -: 2178:			_GLIBCXX_FORWARD(_Arg, __v), __an);
        -: 2179:    }
        -: 2180:
        -: 2181:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2182:	   typename _Compare, typename _Alloc>
        -: 2183:    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2184:			   _Compare, _Alloc>::_Base_ptr,
        -: 2185:	 typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2186:			   _Compare, _Alloc>::_Base_ptr>
       13: 2187:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2188:    _M_get_insert_hint_unique_pos(const_iterator __position,
        -: 2189:				  const key_type& __k)
        -: 2190:    {
       13: 2191:      iterator __pos = __position._M_const_cast();
        -: 2192:      typedef pair<_Base_ptr, _Base_ptr> _Res;
        -: 2193:
        -: 2194:      // end()
       13: 2195:      if (__pos._M_node == _M_end())
        -: 2196:	{
       13: 2197:	  if (size() > 0
       13: 2198:	      && _M_impl._M_key_compare(_S_key(_M_rightmost()), __k))
       12: 2199:	    return _Res(0, _M_rightmost());
        -: 2200:	  else
        1: 2201:	    return _M_get_insert_unique_pos(__k);
        -: 2202:	}
    #####: 2203:      else if (_M_impl._M_key_compare(__k, _S_key(__pos._M_node)))
        -: 2204:	{
        -: 2205:	  // First, try before...
    #####: 2206:	  iterator __before = __pos;
    #####: 2207:	  if (__pos._M_node == _M_leftmost()) // begin()
    #####: 2208:	    return _Res(_M_leftmost(), _M_leftmost());
    #####: 2209:	  else if (_M_impl._M_key_compare(_S_key((--__before)._M_node), __k))
        -: 2210:	    {
    #####: 2211:	      if (_S_right(__before._M_node) == 0)
    #####: 2212:		return _Res(0, __before._M_node);
        -: 2213:	      else
    #####: 2214:		return _Res(__pos._M_node, __pos._M_node);
        -: 2215:	    }
        -: 2216:	  else
    #####: 2217:	    return _M_get_insert_unique_pos(__k);
        -: 2218:	}
    #####: 2219:      else if (_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
        -: 2220:	{
        -: 2221:	  // ... then try after.
    #####: 2222:	  iterator __after = __pos;
    #####: 2223:	  if (__pos._M_node == _M_rightmost())
    #####: 2224:	    return _Res(0, _M_rightmost());
    #####: 2225:	  else if (_M_impl._M_key_compare(__k, _S_key((++__after)._M_node)))
        -: 2226:	    {
    #####: 2227:	      if (_S_right(__pos._M_node) == 0)
    #####: 2228:		return _Res(0, __pos._M_node);
        -: 2229:	      else
    #####: 2230:		return _Res(__after._M_node, __after._M_node);
        -: 2231:	    }
        -: 2232:	  else
    #####: 2233:	    return _M_get_insert_unique_pos(__k);
        -: 2234:	}
        -: 2235:      else
        -: 2236:	// Equivalent keys.
    #####: 2237:	return _Res(__pos._M_node, 0);
        -: 2238:    }
        -: 2239:
        -: 2240:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2241:	   typename _Compare, typename _Alloc>
        -: 2242:#if __cplusplus >= 201103L
        -: 2243:    template<typename _Arg, typename _NodeGen>
        -: 2244:#else
        -: 2245:    template<typename _NodeGen>
        -: 2246:#endif
        -: 2247:      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
       13: 2248:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2249:      _M_insert_unique_(const_iterator __position,
        -: 2250:#if __cplusplus >= 201103L
        -: 2251:			_Arg&& __v,
        -: 2252:#else
        -: 2253:			const _Val& __v,
        -: 2254:#endif
        -: 2255:			_NodeGen& __node_gen)
        -: 2256:    {
       26: 2257:      pair<_Base_ptr, _Base_ptr> __res
       13: 2258:	= _M_get_insert_hint_unique_pos(__position, _KeyOfValue()(__v));
        -: 2259:
       13: 2260:      if (__res.second)
        -: 2261:	return _M_insert_(__res.first, __res.second,
        -: 2262:			  _GLIBCXX_FORWARD(_Arg, __v),
       13: 2263:			  __node_gen);
    #####: 2264:      return iterator(__res.first);
        -: 2265:    }
        -: 2266:
        -: 2267:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2268:	   typename _Compare, typename _Alloc>
        -: 2269:    pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2270:			   _Compare, _Alloc>::_Base_ptr,
        -: 2271:	 typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2272:			   _Compare, _Alloc>::_Base_ptr>
        -: 2273:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2274:    _M_get_insert_hint_equal_pos(const_iterator __position, const key_type& __k)
        -: 2275:    {
        -: 2276:      iterator __pos = __position._M_const_cast();
        -: 2277:      typedef pair<_Base_ptr, _Base_ptr> _Res;
        -: 2278:
        -: 2279:      // end()
        -: 2280:      if (__pos._M_node == _M_end())
        -: 2281:	{
        -: 2282:	  if (size() > 0
        -: 2283:	      && !_M_impl._M_key_compare(__k, _S_key(_M_rightmost())))
        -: 2284:	    return _Res(0, _M_rightmost());
        -: 2285:	  else
        -: 2286:	    return _M_get_insert_equal_pos(__k);
        -: 2287:	}
        -: 2288:      else if (!_M_impl._M_key_compare(_S_key(__pos._M_node), __k))
        -: 2289:	{
        -: 2290:	  // First, try before...
        -: 2291:	  iterator __before = __pos;
        -: 2292:	  if (__pos._M_node == _M_leftmost()) // begin()
        -: 2293:	    return _Res(_M_leftmost(), _M_leftmost());
        -: 2294:	  else if (!_M_impl._M_key_compare(__k, _S_key((--__before)._M_node)))
        -: 2295:	    {
        -: 2296:	      if (_S_right(__before._M_node) == 0)
        -: 2297:		return _Res(0, __before._M_node);
        -: 2298:	      else
        -: 2299:		return _Res(__pos._M_node, __pos._M_node);
        -: 2300:	    }
        -: 2301:	  else
        -: 2302:	    return _M_get_insert_equal_pos(__k);
        -: 2303:	}
        -: 2304:      else
        -: 2305:	{
        -: 2306:	  // ... then try after.
        -: 2307:	  iterator __after = __pos;
        -: 2308:	  if (__pos._M_node == _M_rightmost())
        -: 2309:	    return _Res(0, _M_rightmost());
        -: 2310:	  else if (!_M_impl._M_key_compare(_S_key((++__after)._M_node), __k))
        -: 2311:	    {
        -: 2312:	      if (_S_right(__pos._M_node) == 0)
        -: 2313:		return _Res(0, __pos._M_node);
        -: 2314:	      else
        -: 2315:		return _Res(__after._M_node, __after._M_node);
        -: 2316:	    }
        -: 2317:	  else
        -: 2318:	    return _Res(0, 0);
        -: 2319:	}
        -: 2320:    }
        -: 2321:
        -: 2322:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2323:	   typename _Compare, typename _Alloc>
        -: 2324:#if __cplusplus >= 201103L
        -: 2325:    template<typename _Arg, typename _NodeGen>
        -: 2326:#else
        -: 2327:    template<typename _NodeGen>
        -: 2328:#endif
        -: 2329:      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 2330:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2331:      _M_insert_equal_(const_iterator __position,
        -: 2332:#if __cplusplus >= 201103L
        -: 2333:		       _Arg&& __v,
        -: 2334:#else
        -: 2335:		       const _Val& __v,
        -: 2336:#endif
        -: 2337:		       _NodeGen& __node_gen)
        -: 2338:      {
        -: 2339:	pair<_Base_ptr, _Base_ptr> __res
        -: 2340:	  = _M_get_insert_hint_equal_pos(__position, _KeyOfValue()(__v));
        -: 2341:
        -: 2342:	if (__res.second)
        -: 2343:	  return _M_insert_(__res.first, __res.second,
        -: 2344:			    _GLIBCXX_FORWARD(_Arg, __v),
        -: 2345:			    __node_gen);
        -: 2346:
        -: 2347:	return _M_insert_equal_lower(_GLIBCXX_FORWARD(_Arg, __v));
        -: 2348:      }
        -: 2349:
        -: 2350:#if __cplusplus >= 201103L
        -: 2351:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2352:	   typename _Compare, typename _Alloc>
        -: 2353:    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 2354:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2355:    _M_insert_node(_Base_ptr __x, _Base_ptr __p, _Link_type __z)
        -: 2356:    {
        -: 2357:      bool __insert_left = (__x != 0 || __p == _M_end()
        -: 2358:			    || _M_impl._M_key_compare(_S_key(__z),
        -: 2359:						      _S_key(__p)));
        -: 2360:
        -: 2361:      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
        -: 2362:				    this->_M_impl._M_header);
        -: 2363:      ++_M_impl._M_node_count;
        -: 2364:      return iterator(__z);
        -: 2365:    }
        -: 2366:
        -: 2367:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2368:	   typename _Compare, typename _Alloc>
        -: 2369:    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 2370:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2371:    _M_insert_lower_node(_Base_ptr __p, _Link_type __z)
        -: 2372:    {
        -: 2373:      bool __insert_left = (__p == _M_end()
        -: 2374:			    || !_M_impl._M_key_compare(_S_key(__p),
        -: 2375:						       _S_key(__z)));
        -: 2376:
        -: 2377:      _Rb_tree_insert_and_rebalance(__insert_left, __z, __p,
        -: 2378:				    this->_M_impl._M_header);
        -: 2379:      ++_M_impl._M_node_count;
        -: 2380:      return iterator(__z);
        -: 2381:    }
        -: 2382:
        -: 2383:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2384:	   typename _Compare, typename _Alloc>
        -: 2385:    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 2386:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2387:    _M_insert_equal_lower_node(_Link_type __z)
        -: 2388:    {
        -: 2389:      _Link_type __x = _M_begin();
        -: 2390:      _Base_ptr __y = _M_end();
        -: 2391:      while (__x != 0)
        -: 2392:	{
        -: 2393:	  __y = __x;
        -: 2394:	  __x = !_M_impl._M_key_compare(_S_key(__x), _S_key(__z)) ?
        -: 2395:		_S_left(__x) : _S_right(__x);
        -: 2396:	}
        -: 2397:      return _M_insert_lower_node(__y, __z);
        -: 2398:    }
        -: 2399:
        -: 2400:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2401:	   typename _Compare, typename _Alloc>
        -: 2402:    template<typename... _Args>
        -: 2403:      pair<typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2404:			     _Compare, _Alloc>::iterator, bool>
        -: 2405:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2406:      _M_emplace_unique(_Args&&... __args)
        -: 2407:      {
        -: 2408:	_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
        -: 2409:
        -: 2410:	__try
        -: 2411:	  {
        -: 2412:	    typedef pair<iterator, bool> _Res;
        -: 2413:	    auto __res = _M_get_insert_unique_pos(_S_key(__z));
        -: 2414:	    if (__res.second)
        -: 2415:	      return _Res(_M_insert_node(__res.first, __res.second, __z), true);
        -: 2416:	
        -: 2417:	    _M_drop_node(__z);
        -: 2418:	    return _Res(iterator(__res.first), false);
        -: 2419:	  }
        -: 2420:	__catch(...)
        -: 2421:	  {
        -: 2422:	    _M_drop_node(__z);
        -: 2423:	    __throw_exception_again;
        -: 2424:	  }
        -: 2425:      }
        -: 2426:
        -: 2427:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2428:	   typename _Compare, typename _Alloc>
        -: 2429:    template<typename... _Args>
        -: 2430:      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 2431:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2432:      _M_emplace_equal(_Args&&... __args)
        -: 2433:      {
        -: 2434:	_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
        -: 2435:
        -: 2436:	__try
        -: 2437:	  {
        -: 2438:	    auto __res = _M_get_insert_equal_pos(_S_key(__z));
        -: 2439:	    return _M_insert_node(__res.first, __res.second, __z);
        -: 2440:	  }
        -: 2441:	__catch(...)
        -: 2442:	  {
        -: 2443:	    _M_drop_node(__z);
        -: 2444:	    __throw_exception_again;
        -: 2445:	  }
        -: 2446:      }
        -: 2447:
        -: 2448:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2449:	   typename _Compare, typename _Alloc>
        -: 2450:    template<typename... _Args>
        -: 2451:      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 2452:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2453:      _M_emplace_hint_unique(const_iterator __pos, _Args&&... __args)
        -: 2454:      {
        -: 2455:	_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
        -: 2456:
        -: 2457:	__try
        -: 2458:	  {
        -: 2459:	    auto __res = _M_get_insert_hint_unique_pos(__pos, _S_key(__z));
        -: 2460:
        -: 2461:	    if (__res.second)
        -: 2462:	      return _M_insert_node(__res.first, __res.second, __z);
        -: 2463:
        -: 2464:	    _M_drop_node(__z);
        -: 2465:	    return iterator(__res.first);
        -: 2466:	  }
        -: 2467:	__catch(...)
        -: 2468:	  {
        -: 2469:	    _M_drop_node(__z);
        -: 2470:	    __throw_exception_again;
        -: 2471:	  }
        -: 2472:      }
        -: 2473:
        -: 2474:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2475:	   typename _Compare, typename _Alloc>
        -: 2476:    template<typename... _Args>
        -: 2477:      typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::iterator
        -: 2478:      _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2479:      _M_emplace_hint_equal(const_iterator __pos, _Args&&... __args)
        -: 2480:      {
        -: 2481:	_Link_type __z = _M_create_node(std::forward<_Args>(__args)...);
        -: 2482:
        -: 2483:	__try
        -: 2484:	  {
        -: 2485:	    auto __res = _M_get_insert_hint_equal_pos(__pos, _S_key(__z));
        -: 2486:
        -: 2487:	    if (__res.second)
        -: 2488:	      return _M_insert_node(__res.first, __res.second, __z);
        -: 2489:
        -: 2490:	    return _M_insert_equal_lower_node(__z);
        -: 2491:	  }
        -: 2492:	__catch(...)
        -: 2493:	  {
        -: 2494:	    _M_drop_node(__z);
        -: 2495:	    __throw_exception_again;
        -: 2496:	  }
        -: 2497:      }
        -: 2498:#endif
        -: 2499:
        -: 2500:
        -: 2501:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2502:	   typename _Compare, typename _Alloc>
        -: 2503:    void
        -: 2504:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2505:    _M_erase_aux(const_iterator __position)
        -: 2506:    {
        -: 2507:      _Link_type __y =
        -: 2508:	static_cast<_Link_type>(_Rb_tree_rebalance_for_erase
        -: 2509:				(const_cast<_Base_ptr>(__position._M_node),
        -: 2510:				 this->_M_impl._M_header));
        -: 2511:      _M_drop_node(__y);
        -: 2512:      --_M_impl._M_node_count;
        -: 2513:    }
        -: 2514:
        -: 2515:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2516:	   typename _Compare, typename _Alloc>
        -: 2517:    void
        -: 2518:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2519:    _M_erase_aux(const_iterator __first, const_iterator __last)
        -: 2520:    {
        -: 2521:      if (__first == begin() && __last == end())
        -: 2522:	clear();
        -: 2523:      else
        -: 2524:	while (__first != __last)
        -: 2525:	  _M_erase_aux(__first++);
        -: 2526:    }
        -: 2527:
        -: 2528:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2529:	   typename _Compare, typename _Alloc>
        -: 2530:    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
        -: 2531:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2532:    erase(const _Key& __x)
        -: 2533:    {
        -: 2534:      pair<iterator, iterator> __p = equal_range(__x);
        -: 2535:      const size_type __old_size = size();
        -: 2536:      _M_erase_aux(__p.first, __p.second);
        -: 2537:      return __old_size - size();
        -: 2538:    }
        -: 2539:
        -: 2540:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2541:	   typename _Compare, typename _Alloc>
        -: 2542:    void
        -: 2543:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2544:    erase(const _Key* __first, const _Key* __last)
        -: 2545:    {
        -: 2546:      while (__first != __last)
        -: 2547:	erase(*__first++);
        -: 2548:    }
        -: 2549:
        -: 2550:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2551:	   typename _Compare, typename _Alloc>
        -: 2552:    typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2553:		      _Compare, _Alloc>::iterator
      144: 2554:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2555:    find(const _Key& __k)
        -: 2556:    {
      144: 2557:      iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
      144: 2558:      return (__j == end()
      144: 2559:	      || _M_impl._M_key_compare(__k,
     288*: 2560:					_S_key(__j._M_node))) ? end() : __j;
        -: 2561:    }
        -: 2562:
        -: 2563:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2564:	   typename _Compare, typename _Alloc>
        -: 2565:    typename _Rb_tree<_Key, _Val, _KeyOfValue,
        -: 2566:		      _Compare, _Alloc>::const_iterator
        -: 2567:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2568:    find(const _Key& __k) const
        -: 2569:    {
        -: 2570:      const_iterator __j = _M_lower_bound(_M_begin(), _M_end(), __k);
        -: 2571:      return (__j == end()
        -: 2572:	      || _M_impl._M_key_compare(__k,
        -: 2573:					_S_key(__j._M_node))) ? end() : __j;
        -: 2574:    }
        -: 2575:
        -: 2576:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2577:	   typename _Compare, typename _Alloc>
        -: 2578:    typename _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::size_type
        -: 2579:    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
        -: 2580:    count(const _Key& __k) const
        -: 2581:    {
        -: 2582:      pair<const_iterator, const_iterator> __p = equal_range(__k);
        -: 2583:      const size_type __n = std::distance(__p.first, __p.second);
        -: 2584:      return __n;
        -: 2585:    }
        -: 2586:
        -: 2587:  _GLIBCXX_PURE unsigned int
        -: 2588:  _Rb_tree_black_count(const _Rb_tree_node_base* __node,
        -: 2589:		       const _Rb_tree_node_base* __root) throw ();
        -: 2590:
        -: 2591:  template<typename _Key, typename _Val, typename _KeyOfValue,
        -: 2592:	   typename _Compare, typename _Alloc>
        -: 2593:    bool
        -: 2594:    _Rb_tree<_Key,_Val,_KeyOfValue,_Compare,_Alloc>::__rb_verify() const
        -: 2595:    {
        -: 2596:      if (_M_impl._M_node_count == 0 || begin() == end())
        -: 2597:	return _M_impl._M_node_count == 0 && begin() == end()
        -: 2598:	       && this->_M_impl._M_header._M_left == _M_end()
        -: 2599:	       && this->_M_impl._M_header._M_right == _M_end();
        -: 2600:
        -: 2601:      unsigned int __len = _Rb_tree_black_count(_M_leftmost(), _M_root());
        -: 2602:      for (const_iterator __it = begin(); __it != end(); ++__it)
        -: 2603:	{
        -: 2604:	  _Const_Link_type __x = static_cast<_Const_Link_type>(__it._M_node);
        -: 2605:	  _Const_Link_type __L = _S_left(__x);
        -: 2606:	  _Const_Link_type __R = _S_right(__x);
        -: 2607:
        -: 2608:	  if (__x->_M_color == _S_red)
        -: 2609:	    if ((__L && __L->_M_color == _S_red)
        -: 2610:		|| (__R && __R->_M_color == _S_red))
        -: 2611:	      return false;
        -: 2612:
        -: 2613:	  if (__L && _M_impl._M_key_compare(_S_key(__x), _S_key(__L)))
        -: 2614:	    return false;
        -: 2615:	  if (__R && _M_impl._M_key_compare(_S_key(__R), _S_key(__x)))
        -: 2616:	    return false;
        -: 2617:
        -: 2618:	  if (!__L && !__R && _Rb_tree_black_count(__x, _M_root()) != __len)
        -: 2619:	    return false;
        -: 2620:	}
        -: 2621:
        -: 2622:      if (_M_leftmost() != _Rb_tree_node_base::_S_minimum(_M_root()))
        -: 2623:	return false;
        -: 2624:      if (_M_rightmost() != _Rb_tree_node_base::_S_maximum(_M_root()))
        -: 2625:	return false;
        -: 2626:      return true;
        -: 2627:    }
        -: 2628:
        -: 2629:#if __cplusplus > 201402L
        -: 2630:  // Allow access to internals of compatible _Rb_tree specializations.
        -: 2631:  template<typename _Key, typename _Val, typename _Sel, typename _Cmp1,
        -: 2632:	   typename _Alloc, typename _Cmp2>
        -: 2633:    struct _Rb_tree_merge_helper<_Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>,
        -: 2634:				 _Cmp2>
        -: 2635:    {
        -: 2636:    private:
        -: 2637:      friend class _Rb_tree<_Key, _Val, _Sel, _Cmp1, _Alloc>;
        -: 2638:
        -: 2639:      static auto&
        -: 2640:      _S_get_impl(_Rb_tree<_Key, _Val, _Sel, _Cmp2, _Alloc>& __tree)
        -: 2641:      { return __tree._M_impl; }
        -: 2642:    };
        -: 2643:#endif // C++17
        -: 2644:
        -: 2645:_GLIBCXX_END_NAMESPACE_VERSION
        -: 2646:} // namespace
        -: 2647:
        -: 2648:#endif
